{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number of Paths with Max Score"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: pathsWithMaxScore"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最大得分的路径数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个正方形字符数组&nbsp;<code>board</code>&nbsp;，你从数组最右下方的字符&nbsp;<code>&#39;S&#39;</code>&nbsp;出发。</p>\n",
    "\n",
    "<p>你的目标是到达数组最左上角的字符&nbsp;<code>&#39;E&#39;</code> ，数组剩余的部分为数字字符&nbsp;<code>1, 2, ..., 9</code>&nbsp;或者障碍 <code>&#39;X&#39;</code>。在每一步移动中，你可以向上、向左或者左上方移动，可以移动的前提是到达的格子没有障碍。</p>\n",
    "\n",
    "<p>一条路径的 「得分」 定义为：路径上所有数字的和。</p>\n",
    "\n",
    "<p>请你返回一个列表，包含两个整数：第一个整数是 「得分」 的最大值，第二个整数是得到最大得分的方案数，请把结果对&nbsp;<strong><code>10^9 + 7</code></strong> <strong>取余</strong>。</p>\n",
    "\n",
    "<p>如果没有任何路径可以到达终点，请返回&nbsp;<code>[0, 0]</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>board = [&quot;E23&quot;,&quot;2X2&quot;,&quot;12S&quot;]\n",
    "<strong>输出：</strong>[7,1]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>board = [&quot;E12&quot;,&quot;1X1&quot;,&quot;21S&quot;]\n",
    "<strong>输出：</strong>[4,2]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>board = [&quot;E11&quot;,&quot;XXX&quot;,&quot;11S&quot;]\n",
    "<strong>输出：</strong>[0,0]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= board.length == board[i].length &lt;= 100</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-paths-with-max-score](https://leetcode.cn/problems/number-of-paths-with-max-score/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-paths-with-max-score](https://leetcode.cn/problems/number-of-paths-with-max-score/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"E23\",\"2X2\",\"12S\"]\\r', '[\"E12\",\"1X1\",\"21S\"]\\r', '[\"E11\",\"XXX\",\"11S\"]\\r']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathsWithMaxScore(self, nums: List[str]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        f = [[-inf] * n for _ in range(n)]\n",
    "        g = [[0] * n for _ in range(n)]\n",
    "        MOD = 10 ** 9 + 7\n",
    "        g[0][0] = 1\n",
    "        f[0][0] = 0\n",
    "        for i in range(1, n):\n",
    "            if nums[i][0] != 'X':\n",
    "                f[i][0] = f[i - 1][0] + int(nums[i][0])\n",
    "                g[i][0] = 1\n",
    "        for i in range(1, n):\n",
    "            if nums[0][i] != 'X':\n",
    "                f[0][i] = f[0][i - 1] + int(nums[0][i])\n",
    "                g[0][i] = 1\n",
    "        for i in range(1, n):\n",
    "            for j in range(1, n):\n",
    "                if nums[i][j] != 'X':\n",
    "                    f[i][j] = max(f[i - 1][j], f[i][j - 1], f[i - 1][j - 1])\n",
    "                    if f[i][j] == f[i - 1][j]:\n",
    "                        g[i][j] = (g[i][j] + g[i - 1][j]) % MOD\n",
    "                    if f[i][j] == f[i][j - 1]:\n",
    "                        g[i][j] = (g[i][j] + g[i][j - 1]) % MOD\n",
    "                    if f[i][j] == f[i - 1][j - 1]:\n",
    "                        g[i][j] = (g[i][j] + g[i - 1][j - 1]) % MOD\n",
    "                    if nums[i][j] != 'S':\n",
    "                        f[i][j] += int(nums[i][j])\n",
    "        if f[n - 1][n - 1] < 0:\n",
    "            return [0, 0]\n",
    "        return [f[n - 1][n - 1], g[n - 1][n - 1] % MOD]\n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathsWithMaxScore(self, board: List[str]) -> List[int]:\n",
    "        n = len(board)\n",
    "        mod = 10 ** 9 + 7\n",
    "        dp = [[-inf] * n for _ in range(n)]\n",
    "        cost = [[0] * n for _ in range(n)]\n",
    "\n",
    "        dp[0][0] = 0\n",
    "        cost[0][0] = 1\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if board[i][j] == \"X\":\n",
    "                    continue\n",
    "                elif board[i][j] == \"E\" or board[i][j] == \"S\":\n",
    "                    board_val = 0\n",
    "                else:\n",
    "                    board_val = int(board[i][j])\n",
    "\n",
    "                if i == 0 and j >= 1:\n",
    "                    if not cost[i][j-1]:\n",
    "                        board_val = 0\n",
    "                    dp[i][j] = dp[i][j-1] + board_val\n",
    "                    cost[i][j] = cost[i][j-1]\n",
    "                \n",
    "                if i > 0 and j == 0:\n",
    "                    if not cost[i-1][j]:\n",
    "                        board_val = 0\n",
    "                    dp[i][j] = dp[i-1][j] +board_val\n",
    "                    cost[i][j] = cost[i-1][j]\n",
    "                \n",
    "                if i >= 1 and j >= 1:\n",
    "                    dp[i][j] = max(dp[i-1][j], dp[i-1][j-1], dp[i][j-1])\n",
    "                \n",
    "                    if dp[i][j] == dp[i-1][j]:\n",
    "                        cost[i][j] += cost[i-1][j]\n",
    "                    if dp[i][j] == dp[i-1][j-1]:\n",
    "                        cost[i][j] += cost[i-1][j-1]\n",
    "                    if dp[i][j] == dp[i][j-1]:\n",
    "                        cost[i][j] += cost[i][j-1]\n",
    "                    dp[i][j] += board_val\n",
    "        return [dp[-1][-1] % mod if dp[-1][-1] != -inf else 0, cost[-1][-1] % mod]\n",
    "                        \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathsWithMaxScore(self, board: List[str]) -> List[int]:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        m, n = len(board), len(board[0])\n",
    "        score_m = [[-1] * n for _ in range(m)]\n",
    "        plan_m = [[-1] * n for _ in range(m)]\n",
    "        score_m[0][0] = 0\n",
    "        plan_m[0][0] = 1\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if board[i][j] == 'X':\n",
    "                    continue\n",
    "                maxx_score = -1\n",
    "                for pi, pj in [(i - 1, j - 1), (i - 1, j), (i, j - 1)]:\n",
    "                    if 0 <= pi < m and 0 <= pj < n:\n",
    "                        maxx_score = max(maxx_score, score_m[pi][pj])\n",
    "                if maxx_score == -1:\n",
    "                    continue\n",
    "                score_m[i][j] = maxx_score\n",
    "                if ord(\"0\") <= ord(board[i][j]) <= ord(\"9\"):\n",
    "                    score_m[i][j] += int(board[i][j])\n",
    "                maxx_plans = 0\n",
    "                for pi, pj in [(i - 1, j - 1), (i - 1, j), (i, j - 1)]:\n",
    "                    if 0 <= pi < m and 0 <= pj < n and maxx_score == score_m[pi][pj]:\n",
    "                        maxx_plans += plan_m[pi][pj]\n",
    "                plan_m[i][j] = maxx_plans % MOD\n",
    "        return [0, 0] if score_m[m - 1][n - 1] == -1 else [score_m[m - 1][n - 1], plan_m[m - 1][n - 1]]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathsWithMaxScore(self, board: List[str]) -> List[int]:\n",
    "        m, n = len(board), len(board[0])\n",
    "        score_dp = [[0] * (n) for _ in range(m)]\n",
    "        cnt_dp = [[0] * (n) for _ in range(m)]\n",
    "        cnt_dp[0][0] = 1\n",
    "\n",
    "        def getInt(c):\n",
    "            if c == 'S':\n",
    "                return 0\n",
    "            return ord(c) - ord('0')\n",
    "\n",
    "        # 获取分数和操作步骤\n",
    "        def getScoreAndCnt(r, c):\n",
    "            if r >= 0 and c >= 0:\n",
    "                return [score_dp[r][c], cnt_dp[r][c]]\n",
    "            return [0, 0]\n",
    "\n",
    "        for i in range(0, n):\n",
    "            for j in range(0, m):\n",
    "                if board[i][j] in 'XE':\n",
    "                    continue\n",
    "                score0, cnt0 = getScoreAndCnt(i - 1, j)\n",
    "                score1, cnt1 = getScoreAndCnt(i, j - 1)\n",
    "                score2, cnt2 = getScoreAndCnt(i - 1, j - 1)\n",
    "                # 获取最大分数\n",
    "                max_score = max(score0, score1, score2)\n",
    "                score_dp[i][j] = max_score + getInt(board[i][j])\n",
    "                # 从前面步骤能够获取到最大值，那么才能从前面那个步骤走到这里。\n",
    "                if score0 == max_score:\n",
    "                    cnt_dp[i][j] += cnt0\n",
    "                if score1 == max_score:\n",
    "                    cnt_dp[i][j] += cnt1\n",
    "                if score2 == max_score:\n",
    "                    cnt_dp[i][j] += cnt2\n",
    "\n",
    "        mod = 10**9 + 7\n",
    "        if cnt_dp[m - 1][n - 1] == 0:\n",
    "            return [0, 0]\n",
    "        return [score_dp[m - 1][n - 1] % mod, cnt_dp[m - 1][n - 1] % mod]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathsWithMaxScore(self, board: List[str]) -> List[int]:\n",
    "        mod = 10**9 + 7\n",
    "\n",
    "        n, m = len(board), len(board[0])\n",
    "        dp  = [[-1] * n for _ in range(m)]\n",
    "        cou = [[0] * n for _ in range(m)]\n",
    "\n",
    "        dp[0][0]  = 0\n",
    "        cou[0][0] = 1\n",
    "        for j in range(1, n):\n",
    "            if board[0][j] == 'X':\n",
    "                break\n",
    "            else:\n",
    "                dp[0][j] = dp[0][j - 1] + int(board[0][j])\n",
    "                cou[0][j] = cou[0][j - 1]\n",
    "\n",
    "        for i in range(1, n):\n",
    "            if board[i][0] == 'X':\n",
    "                break\n",
    "            else:\n",
    "                dp[i][0] = dp[i - 1][0] + int(board[i][0])\n",
    "                cou[i][0] = cou[i - 1][0]\n",
    "        #print(cou)\n",
    "\n",
    "        shif = [[0, -1], [-1, 0], [-1, -1]]\n",
    "\n",
    "        for i in range(1, n):\n",
    "            for j in range(1, m):\n",
    "                if board[i][j] == 'X':\n",
    "                    continue\n",
    "\n",
    "                res  = -math.inf\n",
    "                step = 0\n",
    "\n",
    "                for delx, dely in shif:\n",
    "                    nx, ny = i + delx, j + dely\n",
    "                    if 0 <= nx < n and 0 <= ny < m and dp[nx][ny] != -1:\n",
    "                        if res < dp[nx][ny]:\n",
    "                            res  = dp[nx][ny]\n",
    "                            step = cou[nx][ny]\n",
    "                            step %= mod\n",
    "                        elif res == dp[nx][ny]:\n",
    "                            step += cou[nx][ny]\n",
    "                            step %= mod\n",
    "                        #print(step, i, j)\n",
    "                if res != -math.inf:\n",
    "                    if board[i][j] != 'S':\n",
    "                        dp[i][j]  = res + int(board[i][j])\n",
    "                    else:\n",
    "                        dp[i][j]  = res\n",
    "\n",
    "                cou[i][j] = step\n",
    "        \n",
    "        return [dp[n - 1][m - 1], cou[n - 1][m - 1]] if dp[n - 1][m - 1] != -1 else [0, 0]\n",
    "\n",
    "                    \n",
    "\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathsWithMaxScore(self, board: List[str]) -> List[int]:\n",
    "        m,n=len(board),len(board[0])\n",
    "        score_dp=[[0]*(n) for _ in range(m)]\n",
    "        cnt_dp=[[0]*(n) for _ in range(m)]\n",
    "        cnt_dp[0][0]=1\n",
    "        def getInt(c):\n",
    "            if c=='S':\n",
    "                return 0\n",
    "            return ord(c)-ord('0')\n",
    " \n",
    "        for i in range(0,n):\n",
    "            for j in range(0,m):\n",
    "                if board[i][j]=='X' or board[i][j]=='E':\n",
    "                    continue\n",
    "                score0=cnt0=0\n",
    "                score1=cnt1=0\n",
    "                score2=cnt2=0\n",
    "                if i>0:\n",
    "                    score0=score_dp[i-1][j]\n",
    "                    cnt0=cnt_dp[i-1][j]         \n",
    "                if j>0:\n",
    "                    score1=score_dp[i][j-1]\n",
    "                    cnt1=cnt_dp[i][j-1]\n",
    "                if i>=1 and j>=1:\n",
    "                    score2=score_dp[i-1][j-1]\n",
    "                    cnt2=cnt_dp[i-1][j-1]\n",
    "\n",
    "                max_score=max(score0,score1,score2)\n",
    "                score_dp[i][j]=max_score+getInt(board[i][j])\n",
    "                if score0==max_score:\n",
    "                    cnt_dp[i][j]+=cnt0\n",
    "                if score1==max_score:\n",
    "                    cnt_dp[i][j]+=cnt1      \n",
    "                if score2==max_score:\n",
    "                    cnt_dp[i][j]+=cnt2\n",
    "\n",
    "        mod=10**9+7\n",
    "        if cnt_dp[m-1][n-1]==0:\n",
    "            return [0,0]\n",
    "        return [score_dp[m-1][n-1]%mod,cnt_dp[m-1][n-1]%mod]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathsWithMaxScore(self, board: List[str]) -> List[int]:\n",
    "        n = len(board)\n",
    "        g = [list(line) for line in board]  \n",
    "        f = [[0] * n for _ in range(n)]\n",
    "        cnt = [[0] * n for _ in range(n)]  ##方案数\n",
    "        g[0][0] = '0'\n",
    "        cnt[-1][-1] = 1\n",
    "\n",
    "        MOD = int(1e9 + 7)\n",
    "        DIR = [(0, 1), (1, 0), (1, 1)]\n",
    "\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                if (i == n - 1 and j == n - 1) or g[i][j] == 'X':\n",
    "                    continue\n",
    "                maxScore, cntScore = -1, 0\n",
    "                for dx, dy in DIR:\n",
    "                    a, b = i + dx, j + dy\n",
    "                    if a >= n or b >= n or g[a][b] == 'X':\n",
    "                        continue\n",
    "                    if f[a][b] == 0 and (a != n - 1 or b != n - 1):\n",
    "                        continue\n",
    "                    f[i][j] = max(f[i][j], f[a][b] + int(g[i][j]))\n",
    "                    if maxScore < f[a][b]:\n",
    "                        maxScore, cntScore = f[a][b], cnt[a][b]\n",
    "                    elif maxScore == f[a][b]:\n",
    "                        cntScore = (cntScore + cnt[a][b]) % MOD\n",
    "                cnt[i][j] = cntScore\n",
    "\n",
    "        return [f[0][0], cnt[0][0]]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathsWithMaxScore(self, board: List[str]) -> List[int]:\n",
    "        mod = 10 ** 9 + 7\n",
    "        n = len(board)\n",
    "        dp = [[-inf] * n for _ in range(n)]\n",
    "        cost = [[0] * n for _ in range(n)]\n",
    "\n",
    "        dp[0][0] = 0\n",
    "        cost[0][0] = 1\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if board[i][j] == \"X\":\n",
    "                    continue\n",
    "                elif board[i][j] == \"S\" or board[i][j] == \"E\":\n",
    "                    board_val = 0\n",
    "                else:\n",
    "                    board_val = int(board[i][j])\n",
    "                \n",
    "                if i == 0 and j >= 1:\n",
    "                    if not cost[i][j-1]:\n",
    "                        board_val = 0\n",
    "                    dp[i][j] = dp[i][j-1] + board_val\n",
    "                    cost[i][j] = cost[i][j-1]\n",
    "                if j == 0 and i > 0:\n",
    "                    if not cost[i-1][j]:\n",
    "                        board_val = 0\n",
    "                    dp[i][j] = dp[i-1][j] + board_val\n",
    "                    cost[i][j] = cost[i-1][j]\n",
    "                if i >= 1 and j >= 1:\n",
    "                    dp[i][j] = max(dp[i][j-1], dp[i-1][j], dp[i-1][j-1])\n",
    "                \n",
    "                    if dp[i][j] == dp[i-1][j-1]:\n",
    "                        cost[i][j] += cost[i-1][j-1]\n",
    "                    if dp[i][j] == dp[i][j-1]:\n",
    "                        cost[i][j] += cost[i][j-1]\n",
    "                    if dp[i][j] == dp[i-1][j]:\n",
    "                        cost[i][j] += cost[i-1][j]\n",
    "                    \n",
    "                    dp[i][j] += board_val\n",
    "        \n",
    "        return [dp[-1][-1]%mod if dp[-1][-1] != -inf else 0, cost[-1][-1]%mod]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathsWithMaxScore(self, board: List[str]) -> List[int]:\n",
    "        mod = 10 ** 9 + 7\n",
    "        n,m = len(board),len(board[0])\n",
    "        dp1 = [[-float('inf') for _ in range(m)] for _ in range(n)]\n",
    "        dp2 = [[0 for _ in range(m)] for _ in range(n)]\n",
    "        d = [(0,-1),(-1,0),(-1,-1)]\n",
    "        def sc(x,y):\n",
    "            if board[x][y] in ['X','S','E']:\n",
    "                return 0\n",
    "            return int(board[x][y])\n",
    "        def valid(x,y):\n",
    "            return x >= 0 and x < n and y < m and y >= 0 and board[x][y] != 'X'\n",
    "        dp1[0][0] = 0\n",
    "        dp2[0][0] = 1\n",
    "        for x in range(n):\n",
    "            for y in range(m):\n",
    "                if board[x][y] != 'X':\n",
    "                    for dx,dy in d:\n",
    "                        nx,ny = x + dx,y + dy\n",
    "                        if valid(nx,ny):\n",
    "                            c = sc(x,y)\n",
    "                            if dp1[nx][ny] + c == dp1[x][y]:\n",
    "                                dp2[x][y] += dp2[nx][ny]\n",
    "                                dp2[x][y] %= mod\n",
    "                            else:\n",
    "                                if dp1[nx][ny] + c > dp1[x][y]:\n",
    "                                    dp2[x][y] = dp2[nx][ny]\n",
    "                                    dp1[x][y] = dp1[nx][ny] + c\n",
    "        res = [0,dp2[-1][-1]]\n",
    "        if dp1[-1][-1] != -float('inf'):\n",
    "            res[0] = dp1[-1][-1]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathsWithMaxScore(self, board: List[str]) -> List[int]:\n",
    "\n",
    "        dp = [[0]*len(board[0]) for _ in range(len(board))]\n",
    "        max_path = [[0]*len(board[0]) for _ in range(len(board))]\n",
    "        max_path[0][0] = 1\n",
    "\n",
    "        for j in range(1,len(board[0])):\n",
    "            if board[0][j] != 'X':\n",
    "                dp[0][j] += dp[0][j-1] + int(board[0][j])\n",
    "                max_path[0][j] = 1\n",
    "            else:\n",
    "                break \n",
    "        \n",
    "        for i in range(1,len(board)):\n",
    "            if board[i][0] != 'X':\n",
    "                dp[i][0] = dp[i-1][0] + int(board[i][0])\n",
    "                max_path[i][0] = 1\n",
    "            else:\n",
    "                break\n",
    "\n",
    "        # 记录一下\n",
    "        for i in range(1,len(board)):\n",
    "            for j in range(1,len(board[0])):\n",
    "                if board[i][j] != 'X':\n",
    "                    dp[i][j] = max(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])\n",
    "\n",
    "                    count = 0\n",
    "                    if dp[i][j] == dp[i-1][j]:\n",
    "                        count += max_path[i-1][j]\n",
    "                    if dp[i][j] == dp[i][j-1]:\n",
    "                        count += max_path[i][j-1]\n",
    "                    if dp[i][j] == dp[i-1][j-1]:\n",
    "                        count += max_path[i-1][j-1]\n",
    "                    max_path[i][j] = count\n",
    "                    if dp[i][j] != 0:\n",
    "                        if board[i][j] != 'S':\n",
    "                            dp[i][j] += int(board[i][j])\n",
    "        return [dp[len(board)-1][len(board[0])-1],max_path[len(board)-1][len(board[0])-1]%(10**9+7)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathsWithMaxScore(self, board: List[str]) -> List[int]:\n",
    "        n = len(board)\n",
    "        g = [list(line) for line in board]  \n",
    "        f = [[0] * n for _ in range(n)]\n",
    "        cnt = [[0] * n for _ in range(n)]  ##方案数\n",
    "        g[0][0] = '0'\n",
    "        cnt[-1][-1] = 1\n",
    "\n",
    "        MOD = int(1e9 + 7)\n",
    "        DIR = [(0, 1), (1, 0), (1, 1)]\n",
    "\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                if (i == n - 1 and j == n - 1) or g[i][j] == 'X':\n",
    "                    continue\n",
    "                maxScore, cntScore = -1, 0\n",
    "                for dx, dy in DIR:\n",
    "                    a, b = i + dx, j + dy\n",
    "                    if a >= n or b >= n or g[a][b] == 'X':\n",
    "                        continue\n",
    "                    if f[a][b] == 0 and (a != n - 1 or b != n - 1):\n",
    "                        continue\n",
    "                    f[i][j] = max(f[i][j], f[a][b] + int(g[i][j]))\n",
    "                    if maxScore < f[a][b]:\n",
    "                        maxScore, cntScore = f[a][b], cnt[a][b]\n",
    "                    elif maxScore == f[a][b]:\n",
    "                        cntScore = (cntScore + cnt[a][b]) % MOD\n",
    "                cnt[i][j] = cntScore\n",
    "\n",
    "        return [f[0][0], cnt[0][0]]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathsWithMaxScore(self, board: List[str]) -> List[int]:\n",
    "        size = len(board)\n",
    "        point = [[0] * size for _ in range(size)]\n",
    "        path = [[0] * size for _ in range(size)]\n",
    "\n",
    "        for i in range(size - 1, -1, -1):\n",
    "            for j in range(size - 1, -1, -1):\n",
    "                if board[i][j] == 'S':\n",
    "                    point[i][j] = 0\n",
    "                    path[i][j] = 1\n",
    "                    continue\n",
    "                if board[i][j] == 'X':\n",
    "                    point[i][j] = 0\n",
    "                    path[i][j] = 0\n",
    "                    continue\n",
    "                cur = 0 if board[i][j] == 'E' else int(board[i][j]) \n",
    "                if (i + 1) < size and path[i + 1][j] != 0:\n",
    "                    if point[i + 1][j] + cur == point[i][j]:\n",
    "                        path[i][j] += path[i + 1][j]\n",
    "                    if point[i + 1][j] + cur > point[i][j]:\n",
    "                        path[i][j] = path[i + 1][j]\n",
    "                        point[i][j] = point[i + 1][j] + cur\n",
    "                if (j + 1) < size and path[i][j + 1] != 0:\n",
    "                    if point[i][j + 1] + cur == point[i][j]:\n",
    "                        path[i][j] += path[i][j + 1]\n",
    "                    if point[i][j + 1] + cur > point[i][j]:\n",
    "                        path[i][j] = path[i][j + 1]\n",
    "                        point[i][j] = point[i][j + 1] + cur\n",
    "                if (i + 1) < size and (j + 1) < size and path[i + 1][j + 1] != 0:\n",
    "                    if point[i + 1][j + 1] + cur == point[i][j]:\n",
    "                        path[i][j] += path[i + 1][j + 1]\n",
    "                    if point[i + 1][j + 1] + cur > point[i][j]:\n",
    "                        path[i][j] = path[i + 1][j + 1]\n",
    "                        point[i][j] = point[i + 1][j + 1] + cur\n",
    "                        \n",
    "        return [point[0][0] % (10 ** 9 + 7), path[0][0] % (10 ** 9 + 7)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathsWithMaxScore(self, board: List[str]) -> List[int]:\n",
    "        n = len(board)\n",
    "        dp = [[-1 for _j in range(n)] for _i in range(n)]\n",
    "        cnt = [[0 for _j in range(n)] for _i in range(n)]\n",
    "        board[-1] = board[-1][:-1] + '0'\n",
    "        dp[0][0] = 0\n",
    "        cnt[0][0] = 1\n",
    "\n",
    "        for i in range(1, n):\n",
    "            if board[i][0] == 'X':\n",
    "                break\n",
    "            dp[i][0] = dp[i - 1][0] + int(board[i][0])\n",
    "            cnt[i][0] = 1\n",
    "        for j in range(1, n):\n",
    "            if board[0][j] == 'X':\n",
    "                break\n",
    "            dp[0][j] = dp[0][j - 1] + int(board[0][j])\n",
    "            cnt[0][j] = 1\n",
    "\n",
    "        for i in range(1, n):\n",
    "            for j in range(1, n):\n",
    "                if board[i][j] == 'X':\n",
    "                    continue\n",
    "                if dp[i][j - 1] >= 0:\n",
    "                    dp[i][j] = max(dp[i][j - 1] + int(board[i][j]), dp[i][j])\n",
    "                if dp[i - 1][j] >= 0:\n",
    "                    dp[i][j] = max(dp[i - 1][j] + int(board[i][j]), dp[i][j])\n",
    "                if dp[i - 1][j - 1] >= 0:\n",
    "                    dp[i][j] = max(dp[i - 1][j - 1] + int(board[i][j]), dp[i][j])\n",
    "\n",
    "                if dp[i][j] == dp[i][j - 1] + int(board[i][j]):\n",
    "                    cnt[i][j] += cnt[i][j - 1]\n",
    "                if dp[i][j] == dp[i - 1][j] + int(board[i][j]):\n",
    "                    cnt[i][j] += cnt[i - 1][j]\n",
    "                if dp[i][j] == dp[i - 1][j - 1] + int(board[i][j]):\n",
    "                    cnt[i][j] += cnt[i - 1][j-1]\n",
    "    \n",
    "        v = dp[-1][-1] if dp[-1][-1]>=0 else 0\n",
    "        c = cnt[-1][-1]\n",
    "        c %= 1000000007\n",
    "        return [v, c]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathsWithMaxScore(self, board: List[str]) -> List[int]:\n",
    "        mod = 10**9 + 7\n",
    "\n",
    "        n, m = len(board), len(board[0])\n",
    "        dp  = [[-1] * n for _ in range(m)]\n",
    "        cou = [[0] * n for _ in range(m)]\n",
    "\n",
    "        dp[0][0]  = 0\n",
    "        cou[0][0] = 1\n",
    "        for j in range(1, n):\n",
    "            if board[0][j] == 'X':\n",
    "                break\n",
    "            else:\n",
    "                dp[0][j] = dp[0][j - 1] + int(board[0][j])\n",
    "                cou[0][j] = cou[0][j - 1]\n",
    "\n",
    "        for i in range(1, n):\n",
    "            if board[i][0] == 'X':\n",
    "                break\n",
    "            else:\n",
    "                dp[i][0] = dp[i - 1][0] + int(board[i][0])\n",
    "                cou[i][0] = cou[i - 1][0]\n",
    "        #print(cou)\n",
    "\n",
    "        shif = [[0, -1], [-1, 0], [-1, -1]]\n",
    "\n",
    "        for i in range(1, n):\n",
    "            for j in range(1, m):\n",
    "                if board[i][j] == 'X':\n",
    "                    continue\n",
    "\n",
    "                res  = -math.inf\n",
    "                step = 0\n",
    "\n",
    "                for delx, dely in shif:\n",
    "                    nx, ny = i + delx, j + dely\n",
    "                    if 0 <= nx < n and 0 <= ny < m and dp[nx][ny] != -1:\n",
    "                        if res < dp[nx][ny]:\n",
    "                            res  = dp[nx][ny]\n",
    "                            step = cou[nx][ny]\n",
    "                            step %= mod\n",
    "                        elif res == dp[nx][ny]:\n",
    "                            step += cou[nx][ny]\n",
    "                            step %= mod\n",
    "                        #print(step, i, j)\n",
    "                if res != -math.inf:\n",
    "                    if board[i][j] != 'S':\n",
    "                        dp[i][j]  = res + int(board[i][j])\n",
    "                    else:\n",
    "                        dp[i][j]  = res\n",
    "\n",
    "                cou[i][j] = step\n",
    "        \n",
    "        return [dp[n - 1][m - 1], cou[n - 1][m - 1]] if dp[n - 1][m - 1] != -1 else [0, 0]\n",
    "\n",
    "                    \n",
    "\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathsWithMaxScore(self, board: List[str]) -> List[int]:\n",
    "        mod = 10**9+7\n",
    "        n = len(board)\n",
    "        distance = [[0 for j in range(n)] for i in range(n)]\n",
    "        count = [[0 for j in range(n)] for i in range(n)]\n",
    "        count[-1][-1] = 1\n",
    "        for i in range(n-1,-1,-1):\n",
    "            for j in range(n-1,-1,-1):\n",
    "                if board[i][j] != 'S' and board[i][j] != 'X':\n",
    "                    max_val = 0\n",
    "                    temp_count = 0\n",
    "                    if i < n-1:\n",
    "                        if board[i+1][j] != 'X':\n",
    "                            if distance[i+1][j] > max_val:\n",
    "                                max_val = distance[i+1][j]\n",
    "                                temp_count = count[i+1][j]\n",
    "                            elif distance[i+1][j] == max_val:\n",
    "                                temp_count += count[i+1][j]\n",
    "                    if j < n-1:\n",
    "                        if board[i][j+1] != 'X':\n",
    "                            if distance[i][j+1] > max_val:\n",
    "                                max_val = distance[i][j+1]\n",
    "                                temp_count = count[i][j+1]\n",
    "                            elif distance[i][j+1] == max_val:\n",
    "                                temp_count += count[i][j+1]\n",
    "                    if i < n-1 and j < n-1:\n",
    "                        if board[i+1][j+1] != 'X':\n",
    "                            if distance[i+1][j+1] > max_val:\n",
    "                                max_val = distance[i+1][j+1]\n",
    "                                temp_count = count[i+1][j+1]\n",
    "                            elif distance[i+1][j+1] == max_val:\n",
    "                                temp_count += count[i+1][j+1]\n",
    "                    if board[i][j]=='E':\n",
    "                        distance[i][j] = max_val\n",
    "                    else:\n",
    "                        distance[i][j] = (int(board[i][j])+max_val)%mod\n",
    "                    count[i][j] = (count[i][j]+temp_count)%mod\n",
    "        if count[0][0] == 0:\n",
    "            return [0,0]\n",
    "        else:\n",
    "            return [distance[0][0],count[0][0]]\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathsWithMaxScore(self, board: List[str]) -> List[int]:\n",
    "        mod=10**9+7\n",
    "        n=len(board)\n",
    "        dp=[[-inf]*n for _ in range(n)]\n",
    "        cost=[[0]*n for _ in range(n)]\n",
    "        # 初始化[0,0]位置\n",
    "        dp[0][0]=0\n",
    "        cost[0][0]=1\n",
    "        # 初始化首行首列\n",
    "        for i in range(1,n):\n",
    "            if board[i][0]=='X':\n",
    "                break\n",
    "            dp[i][0]=dp[i-1][0]+int(board[i][0])\n",
    "            cost[i][0]=1\n",
    "        for i in range(1,n):\n",
    "            if board[0][i]=='X':\n",
    "                break\n",
    "            dp[0][i]=dp[0][i-1]+int(board[0][i])\n",
    "            cost[0][i]=1\n",
    "        # 动态规划\n",
    "        for i in range(1,n):\n",
    "            for j in range(1,n):\n",
    "                if board[i][j]=='X':\n",
    "                    continue\n",
    "                # 计算最大值                \n",
    "                dp[i][j]=max(dp[i-1][j-1],dp[i][j-1],dp[i-1][j])\n",
    "                if dp[i][j]==-inf:continue\n",
    "                if dp[i][j]==dp[i-1][j-1]:\n",
    "                    cost[i][j]+=cost[i-1][j-1]\n",
    "                if dp[i][j]==dp[i][j-1]:\n",
    "                    cost[i][j]+=cost[i][j-1]\n",
    "                if dp[i][j]==dp[i-1][j]:\n",
    "                    cost[i][j]+=cost[i-1][j]\n",
    "                dp[i][j]+=0 if i==n-1 and j==n-1 else int(board[i][j])\n",
    "        # 返回\n",
    "        return [dp[-1][-1]%mod if dp[-1][-1]!=-inf else 0,cost[-1][-1]%mod]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathsWithMaxScore(self, board: List[str]) -> List[int]:\n",
    "        mod = 10 ** 9 + 7\n",
    "        n,m = len(board),len(board[0])\n",
    "        dp1 = [[-float('inf') for _ in range(m)] for _ in range(n)]\n",
    "        dp2 = [[0 for _ in range(m)] for _ in range(n)]\n",
    "        d = [(0,-1),(-1,0),(-1,-1)]\n",
    "        def sc(x,y):\n",
    "            if board[x][y] in ['X','S','E']:\n",
    "                return 0\n",
    "            return int(board[x][y])\n",
    "        def valid(x,y):\n",
    "            return x >= 0 and x < n and y < m and y >= 0 and board[x][y] != 'X'\n",
    "        dp2[0][0] = 1\n",
    "        dp1[0][0] = 0\n",
    "        for x in range(n):\n",
    "            for y in range(m):\n",
    "                if board[x][y] != 'X':\n",
    "                    for dx,dy in d:\n",
    "                        nx,ny = x + dx,y + dy\n",
    "                        if valid(nx,ny):\n",
    "                            c = sc(x,y)\n",
    "                            if dp1[nx][ny] + c == dp1[x][y]:\n",
    "                                dp2[x][y] += dp2[nx][ny]\n",
    "                                dp2[x][y] %= mod\n",
    "                            else:\n",
    "                                if dp1[nx][ny] + c > dp1[x][y]:\n",
    "                                    dp2[x][y] = dp2[nx][ny]\n",
    "                                    dp1[x][y] = dp1[nx][ny] + c\n",
    "        res = [0,dp2[-1][-1]]\n",
    "        if dp1[-1][-1] != -float('inf'):\n",
    "            res[0] = dp1[-1][-1]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathsWithMaxScore(self, board: List[str]) -> List[int]:\n",
    "        Mod = 10 ** 9 + 7\n",
    "        n = len(board)\n",
    "        f = [[0 for i in range(n)] for i in range(n)] # 最大值\n",
    "        g = [[0 for i in range(n)] for i in range(n)] # 方案数\n",
    "        f[0][0] = 0\n",
    "        g[0][0] = 1\n",
    "\n",
    "        for i in range(1,n):\n",
    "            if board[i][0] == 'X':\n",
    "                f[i][0] = -float('inf')\n",
    "            else:\n",
    "                f[i][0] = f[i-1][0] + int(board[i][0])\n",
    "                g[i][0] = g[i-1][0]\n",
    "            if board[0][i] == 'X':\n",
    "                f[0][i] = -float('inf')\n",
    "            else:\n",
    "                f[0][i] = f[0][i-1] + int(board[0][i])\n",
    "                g[0][i] = g[0][i-1]\n",
    "        \n",
    "        for i in range(1,n):\n",
    "            for j in range(1,n):\n",
    "                if board[i][j] == 'X':\n",
    "                    f[i][j] = -float('inf')\n",
    "                else:\n",
    "                    if i == j == n-1:\n",
    "                        cur = 0\n",
    "                    else:\n",
    "                        cur = int(board[i][j])\n",
    "                    max_v = max(f[i-1][j],f[i][j-1],f[i-1][j-1])\n",
    "                    f[i][j] = max_v + cur\n",
    "                    g[i][j] = g[i-1][j] * int(f[i-1][j] == max_v) + g[i-1][j-1] * int(f[i-1][j-1] == max_v)  + g[i][j-1] * int(f[i][j-1] == max_v)\n",
    "        \n",
    "        if f[n-1][n-1] < 0:\n",
    "            a = 0\n",
    "        else:\n",
    "            a = f[n-1][n-1]%Mod\n",
    "        b = g[n-1][n-1]%Mod\n",
    "        return [a,b]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathsWithMaxScore(self, board: List[str]) -> List[int]:\n",
    "        score = []\n",
    "        n, m = len(board), len(board[0])\n",
    "        visited = set((n-1, m-1))\n",
    "        for i in range(n):\n",
    "            line = []\n",
    "            for j in range(m):\n",
    "                c = board[i][j]\n",
    "                if c == 'X':\n",
    "                    line.append('X')\n",
    "                    visited.add((i, j))\n",
    "                elif c == 'E':\n",
    "                    line.append(0)\n",
    "                elif c == 'S':\n",
    "                    line.append('S')\n",
    "                else:\n",
    "                    line.append(int(c))\n",
    "            score.append(line)\n",
    "        #for i in range(n):\n",
    "            #visited.add((i, m))\n",
    "        #for j in range(m):\n",
    "            #visited.add((n, j))\n",
    "\n",
    "        queue = [(n-1, m-1)]\n",
    "        record1 = [[-1] * n  for _ in range(n)]\n",
    "        record2 = [[-1] * n  for _ in range(n)]\n",
    "        record1[n-1][n-1] = 0\n",
    "        record2[n-1][n-1] = 1\n",
    "        s = 0\n",
    "        mod = 10 ** 9 + 7\n",
    "        for i in range(1, n):\n",
    "            xys = []\n",
    "            y = n - 1 - i\n",
    "            for x in range(n - 1, n - 1 - i, -1):\n",
    "                xys.append((x, y))\n",
    "            x = n - 1 - i\n",
    "            for y in range(n - 1, n - 2 - i, -1):\n",
    "                xys.append((x, y))\n",
    "                        \n",
    "            for x, y in xys:\n",
    "                if score[x][y] != 'X':\n",
    "                    currentMax, num1 = -1, -1\n",
    "                    for x2, y2 in [(x+1, y), (x, y+1), (x+1, y+1)]:\n",
    "                        if x2 < n and y2 < m and score[x2][y2] != 'X' and record1[x2][y2] != -1:\n",
    "                            preMax, num2 = record1[x2][y2], record2[x2][y2]\n",
    "                            if currentMax == -1 or currentMax < preMax:\n",
    "                                currentMax, num1 = preMax, num2\n",
    "                            elif currentMax == preMax:\n",
    "                                num1 += num2\n",
    "                    if currentMax != -1:\n",
    "                        record1[x][y] = currentMax + score[x][y]\n",
    "                        record2[x][y] = num1 % mod\n",
    "            \n",
    "        if record1[0][0] == -1:\n",
    "            return [0, 0]\n",
    "        else:\n",
    "            return [record1[0][0], record2[0][0]]\n",
    "'''\n",
    "E 1 1 3 4 5\n",
    "X 4 5 2 X X\n",
    "3 X 4 3 X 4\n",
    "4 4 X 3 1 2\n",
    "2 3 4 5 6 X \n",
    "1 3 4 5 X S\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathsWithMaxScore(self, board: List[str]) -> List[int]:\n",
    "        mod = 10 ** 9 + 7\n",
    "        n = len(board)\n",
    "        scores = [[0 for i in range(n)] for j in range(n)]\n",
    "        count = [[0 for i in range(n)] for j in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if board[i][j] == 'E':\n",
    "                    count[i][j] = 1\n",
    "                    continue\n",
    "\n",
    "                if board[i][j] == 'X':\n",
    "                    scores[i][j] = 0\n",
    "                    count[i][j] = 0\n",
    "                    continue\n",
    "\n",
    "                curPos = board[i][j]\n",
    "                if board[i][j] == 'S':\n",
    "                    curPos = 0\n",
    "                curPos = int(curPos)\n",
    "                if i == 0 and j == 0:\n",
    "                    scores[i][j] = 0\n",
    "                    count[i][j] = 0\n",
    "                elif i == 0:\n",
    "                    scores[i][j] = scores[i][j - 1] + curPos\n",
    "                    count[i][j] = count[i][j - 1]\n",
    "                elif j == 0:\n",
    "                    scores[i][j] = scores[i - 1][j] + curPos\n",
    "                    count[i][j] = count[i - 1][j] \n",
    "                else:\n",
    "                    prevScores = [scores[i][j - 1], scores[i - 1][j], scores[i - 1][j - 1]]\n",
    "                    routeCount = [count[i][j - 1], count[i - 1][j], count[i - 1][j - 1]]\n",
    "                    maxScore = max(prevScores)\n",
    "                    scores[i][j] = maxScore + curPos\n",
    "                    scores[i][j] %= mod\n",
    "                    for score, route in zip(prevScores, routeCount):\n",
    "                        if score == maxScore:\n",
    "                            count[i][j] += route\n",
    "                    count[i][j] %= mod\n",
    "\n",
    "        if count[n - 1][n - 1] == 0:\n",
    "            return [0, 0]\n",
    "        return [scores[n - 1][n - 1], count[n - 1][n - 1]]\n",
    "                    \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathsWithMaxScore(self, board: List[str]) -> List[int]:\n",
    "\n",
    "        dp = [[0]*len(board[0]) for _ in range(len(board))]\n",
    "        max_path = [[0]*len(board[0]) for _ in range(len(board))]\n",
    "        max_path[0][0] = 1\n",
    "    \n",
    "        for j in range(1,len(board[0])):\n",
    "            if board[0][j] != 'X':\n",
    "                dp[0][j] += dp[0][j-1] + int(board[0][j])\n",
    "                max_path[0][j] = 1\n",
    "            else:\n",
    "                break \n",
    "                \n",
    "\n",
    "        for i in range(1,len(board)):\n",
    "            if board[i][0] != 'X':\n",
    "                dp[i][0] = dp[i-1][0] + int(board[i][0])\n",
    "                max_path[i][0] = 1\n",
    "            else:\n",
    "                break\n",
    "\n",
    "        # 记录一下\n",
    "        for i in range(1,len(board)):\n",
    "            for j in range(1,len(board[0])):\n",
    "                if board[i][j] != 'X':\n",
    "                    dp[i][j] = max(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])\n",
    "\n",
    "                    count = 0\n",
    "                    if dp[i][j] == dp[i-1][j]:\n",
    "                        count += max_path[i-1][j]\n",
    "                    if dp[i][j] == dp[i][j-1]:\n",
    "                        count += max_path[i][j-1]\n",
    "                    if dp[i][j] == dp[i-1][j-1]:\n",
    "                        count += max_path[i-1][j-1]\n",
    "                    max_path[i][j] = count\n",
    "                    if dp[i][j] != 0:\n",
    "                        if board[i][j] != 'S':\n",
    "                            dp[i][j] += int(board[i][j])\n",
    "\n",
    "        if dp[len(board)-1][len(board[0])-1] == 0:\n",
    "            return [0,max_path[len(board)-1][len(board[0])-1]%(10**9+7)]\n",
    "        return [dp[len(board)-1][len(board[0])-1],max_path[len(board)-1][len(board[0])-1]%(10**9+7)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "mod = int(1e9)+7\n",
    "class Solution:\n",
    "    def pathsWithMaxScore(self, board: List[str]) -> List[int]:\n",
    "        inf = int(-1e9)\n",
    "        n = len(board)\n",
    "        def get_idx(x,y):\n",
    "            return x*n+y\n",
    "        def update_dp(s,t,cs,ct):\n",
    "            if s>cs:\n",
    "                cs = s\n",
    "                ct = t\n",
    "            elif s==cs:\n",
    "                ct += t\n",
    "            ct = ct%mod\n",
    "            return cs,ct\n",
    "        sdp=[0]*(n*n) #score dp\n",
    "        tdp=[0]*(n*n) #total scheme dp\n",
    "        boards = [[0]*(n) for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if board[i][j]=='X':\n",
    "                    boards[i][j] = inf\n",
    "                elif board[i][j]=='E' or board[i][j]=='S':\n",
    "                    boards[i][j]=0\n",
    "                else:\n",
    "                    boards[i][j] = ord(board[i][j])-ord('0')\n",
    "        for i in range(n-1,-1,-1):\n",
    "            for j in range(n-1,-1,-1):\n",
    "                idx = get_idx(i,j)\n",
    "                if i==n-1 and j==n-1:\n",
    "                    tdp[idx] = 1\n",
    "                    continue\n",
    "                if boards[i][j]==inf:\n",
    "                    sdp[idx] = inf\n",
    "                    continue\n",
    "                cs=inf\n",
    "                ct=0\n",
    "                if i+1<n:\n",
    "                    cs,ct = update_dp(sdp[get_idx(i+1,j)]+boards[i][j],tdp[get_idx(i+1,j)],cs,ct)\n",
    "                if j+1<n:\n",
    "                    cs,ct = update_dp(sdp[get_idx(i,j+1)]+boards[i][j],tdp[get_idx(i,j+1)],cs,ct)\n",
    "                if i+1<n and j+1<n:\n",
    "                    cs,ct = update_dp(sdp[get_idx(i+1,j+1)]+boards[i][j],tdp[get_idx(i+1,j+1)],cs,ct)\n",
    "                sdp[idx] = cs if cs>=0 else inf\n",
    "                tdp[idx] = ct\n",
    "        if sdp[0]==inf:return 0,0\n",
    "        else:return sdp[0],tdp[0]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathsWithMaxScore(self, board: List[str]) -> List[int]:\n",
    "        n = len(board)\n",
    "        mod = 10**9 + 7\n",
    "        dp = [[-inf]*n for _ in range(n)]\n",
    "        dp_num = [[1]*n for _ in range(n)]\n",
    "        dp[n-1][n-1] = 0\n",
    "        dp[0][0] = 0\n",
    "        dp_num[0][0] = 0\n",
    "        print(dp)\n",
    "        for i in range(n-1, -1, -1):\n",
    "            for j in range(n-1, -1, -1):\n",
    "                if board[i][j]==\"X\" or board[i][j]==\"S\":\n",
    "                    continue\n",
    "                if i==0 and j==0:\n",
    "                    add_num = 0\n",
    "                else:\n",
    "                    add_num = int(board[i][j])\n",
    "                if i<n-1 and board[i+1][j]!='X':\n",
    "                    if dp[i+1][j] + add_num>dp[i][j]:\n",
    "                        dp[i][j] = dp[i+1][j] + add_num\n",
    "                        dp_num[i][j] = dp_num[i+1][j]\n",
    "\n",
    "                if j<n-1 and board[i][j+1]!='X':\n",
    "                    if dp[i][j+1] + add_num>dp[i][j]:\n",
    "                        dp[i][j] = (dp[i][j+1] + add_num)\n",
    "                        dp_num[i][j] = dp_num[i][j+1]\n",
    "                    elif dp[i][j+1] + add_num==dp[i][j]:\n",
    "                        dp_num[i][j] += dp_num[i][j+1]\n",
    "\n",
    "                if i<n-1 and j<n-1 and dp[i+1][j+1]!='X':\n",
    "                    if dp[i+1][j+1] + add_num>dp[i][j]:\n",
    "                        dp[i][j] = dp[i+1][j+1] + add_num\n",
    "                        dp_num[i][j] = dp_num[i+1][j+1]\n",
    "                    elif dp[i+1][j+1] + add_num==dp[i][j]:\n",
    "                        dp_num[i][j] += dp_num[i+1][j+1]\n",
    "                dp_num[i][j]%=mod\n",
    "            \n",
    "        print(dp)\n",
    "        print(dp_num)\n",
    "        return [dp[0][0], dp_num[0][0]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathsWithMaxScore(self, board: List[str]) -> List[int]:\n",
    "        n = len(board)\n",
    "        dp = [[[-1, 0]] * n for _ in range(n)]\n",
    "        dp[n - 1][n - 1] = [0, 1]\n",
    "\n",
    "        def update(x, y, u, v):\n",
    "            if u >= n or v >= n or dp[u][v][0] == -1:\n",
    "                return\n",
    "            if dp[u][v][0] > dp[x][y][0]:\n",
    "                dp[x][y] = dp[u][v][:]\n",
    "            elif dp[u][v][0] == dp[x][y][0]:\n",
    "                dp[x][y][1] += dp[u][v][1]\n",
    "\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                if not (i == n - 1 and j == n - 1) and board[i][j] != \"X\":\n",
    "                    update(i, j, i + 1, j)\n",
    "                    update(i, j, i, j + 1)\n",
    "                    update(i, j, i + 1, j + 1)\n",
    "                    if dp[i][j][0] != -1:\n",
    "                        dp[i][j][0] += (0 if board[i][j] == \"E\" else ord(board[i][j]) - 48)\n",
    "        return [dp[0][0][0], dp[0][0][1] % (10**9 + 7)] if dp[0][0][0] != -1 else [0, 0]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathsWithMaxScore(self, board: List[str]) -> List[int]:\n",
    "        m,n = len(board),len(board[0])\n",
    "        dp = [[[0,0] for _ in range(n)] for _ in range(m)]\n",
    "        dp[-1][-1]=[0,1]\n",
    "        board[0]=\"0\"+board[0][1:]\n",
    "        board[-1]=board[-1][:-1]+\"0\"\n",
    "        for i in range(m-1,-1,-1):\n",
    "            for j in range(n-1,-1,-1):\n",
    "                if board[i][j]==\"X\" :\n",
    "                    dp[i][j]=[-float(\"inf\"),0]\n",
    "                    continue\n",
    "                if  i==m-1 and j==n-1:\n",
    "                    continue\n",
    "                canpass=False\n",
    "                if i+1<m and board[i+1][j]!=\"X\" :\n",
    "                    newsum=dp[i+1][j][0]+int(board[i][j])\n",
    "                    if newsum>dp[i][j][0]:\n",
    "                        dp[i][j] =[newsum,dp[i+1][j][1]]\n",
    "                        canpass=True\n",
    "                    elif newsum ==dp[i][j][0]:\n",
    "                        dp[i][j] =[newsum,dp[i+1][j][1]+dp[i][j][1]]\n",
    "                        canpass=True\n",
    "                    # print(\"case 1: \", i,j,dp[i][j])\n",
    "                if j+1<n and board[i][j+1]!=\"X\" :\n",
    "                    newsum=dp[i][j+1][0]+int(board[i][j])\n",
    "                    if newsum>dp[i][j][0]:\n",
    "                        dp[i][j] =[newsum,dp[i][j+1][1]]\n",
    "                        canpass=True\n",
    "                    elif newsum ==dp[i][j][0]:\n",
    "                        dp[i][j] =[newsum,dp[i][j+1][1]+dp[i][j][1]]\n",
    "                        canpass=True\n",
    "                    # print(\"case 2: \", i,j,dp[i][j],dp[i][j+1][1],dp[i][j][1])\n",
    "                if i+1<m and j+1<n and board[i+1][j+1]!=\"X\":\n",
    "                    newsum=dp[i+1][j+1][0]+int(board[i][j])\n",
    "                    if newsum>dp[i][j][0]:\n",
    "                        dp[i][j] =[newsum,dp[i+1][j+1][1]]\n",
    "                        canpass=True\n",
    "                    elif newsum ==dp[i][j][0]:\n",
    "                        dp[i][j] =[newsum,dp[i+1][j+1][1]+dp[i][j][1]]\n",
    "                        canpass=True\n",
    "                    # print(\"case 3: \", i,j,dp[i][j])\n",
    "                if canpass:\n",
    "                    dp[i][j]=[dp[i][j][0]%(10**9+7),dp[i][j][1]%(10**9+7)]\n",
    "                else:\n",
    "                    if i==0 and j==0:\n",
    "                        continue\n",
    "                    else:\n",
    "                        dp[i][j]=[-float(\"inf\"),0]\n",
    "            # print(dp[i])\n",
    "        \n",
    "        return dp[0][0]\n",
    "\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathsWithMaxScore(self, board: List[str]) -> List[int]:\n",
    "        n = len(board)\n",
    "        dp = [[[0] * 2 for _ in range(n)] for _ in range(n)]\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                if board[i][j] == 'X': continue\n",
    "                elif board[i][j] == 'S':\n",
    "                    dp[i][j] = [0, 1]\n",
    "                else:\n",
    "                    for (dr, dc) in [(1, 0), (0, 1), (1, 1)]:\n",
    "                        if 0 <= i + dr < n and 0 <= j + dc < n:\n",
    "                            if dp[i][j][0] < dp[i+dr][j+dc][0]:\n",
    "                                dp[i][j] = list(dp[i+dr][j+dc])\n",
    "                            elif dp[i][j][0] == dp[i+dr][j+dc][0]:\n",
    "                                dp[i][j][1] += dp[i+dr][j+dc][1]\n",
    "                                dp[i][j][1] %= 10 ** 9 + 7\n",
    "                            else:\n",
    "                                continue\n",
    "                    if board[i][j] != 'E' and dp[i][j][1] != 0:\n",
    "                        dp[i][j][0] += int(board[i][j])\n",
    "        \n",
    "        return dp[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathsWithMaxScore(self, board: List[str]) -> List[int]:\n",
    "        dp = [[[0, 0] for _ in range(len(board[0]))] for _ in range(len(board))]\n",
    "        dp[-1][-1] = [0, 1]\n",
    "        for i in range(len(board) - 1, -1, -1):\n",
    "            for j in range(len(board[0]) - 1, -1, -1):\n",
    "                if board[i][j] != 'X':\n",
    "                    for x, y in [(0, 1), (1, 0), (1, 1)]:\n",
    "                        if i + x < len(board) and j + y < len(board[0]):\n",
    "                            if dp[i + x][j + y][0] > dp[i][j][0]:\n",
    "                                dp[i][j] = [dp[i + x][j + y][0], dp[i + x][j + y][1]]\n",
    "                            elif dp[i + x][j + y][0] == dp[i][j][0]:\n",
    "                                dp[i][j][1] += dp[i + x][j + y][1]\n",
    "                    dp[i][j][0] += int(board[i][j]) if board[i][j].isdigit() else 0\n",
    "                    dp[i][j][1] %= 10 ** 9 + 7\n",
    "        return dp[0][0] if dp[0][0][1] else [0, 0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathsWithMaxScore(self, board: List[str]) -> List[int]:\n",
    "        m = len(board)\n",
    "        mat = [([(0, 0) for __ in range(m - 1)] + [(-101, 0)]) for _ in range(m - 1)]\n",
    "        mat.append([(-101, 0) for ___ in range(m - 1)] + [(0, 1)])\n",
    "        for i in range(m - 2, -1, -1):\n",
    "            if board[m - 1][i] == 'X': break\n",
    "            mat[m - 1][i] = (mat[m - 1][i + 1][0] + int(board[m - 1][i]), 1)       \n",
    "        for i in range(m - 2, -1, -1):\n",
    "            if board[i][m - 1] == 'X': break\n",
    "            mat[i][m - 1] = (mat[i + 1][m - 1][0] + int(board[i][m - 1]), 1)  \n",
    "        \n",
    "        for i in range(m - 2, -1, -1):\n",
    "            for j in range(m - 2, -1, -1):\n",
    "                if board[i][j] == 'X':\n",
    "                    mat[i][j] = (-101, 0)\n",
    "                else:\n",
    "                    right = mat[i][j + 1] if board[i][j + 1] != 'X' else (-101, 0)\n",
    "                    down = mat[i + 1][j] if board[i + 1][j] != 'X' else (-101, 0)\n",
    "                    rightDown = mat[i + 1][j + 1] if board[i + 1][j + 1] else (-101, 0)\n",
    "                    path = []\n",
    "                    for k in (right, down, rightDown):\n",
    "                        if not path:\n",
    "                            path.append(k)\n",
    "                        else:\n",
    "                            if k[0] > path[0][0]:\n",
    "                                path = [k]\n",
    "                            elif k[0] == path[0][0]:\n",
    "                                path.append(k)\n",
    "                    mat[i][j] = (path[0][0] + (int(board[i][j]) if board[i][j] != 'E' else 0), sum([l[1] for l in path]))\n",
    "        #print(mat)\n",
    "        if mat[0][0][0] >= 0:\n",
    "            return [mat[0][0][0], mat[0][0][1] % 1000000007]\n",
    "        else:\n",
    "            return [0, 0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathsWithMaxScore(self, board: List[str]) -> List[int]:\n",
    "        score = []\n",
    "        n, m = len(board), len(board[0])\n",
    "        visited = set((n-1, m-1))\n",
    "        for i in range(n):\n",
    "            line = []\n",
    "            for j in range(m):\n",
    "                c = board[i][j]\n",
    "                if c == 'X':\n",
    "                    line.append('X')\n",
    "                    visited.add((i, j))\n",
    "                elif c == 'E':\n",
    "                    line.append(0)\n",
    "                elif c == 'S':\n",
    "                    line.append('S')\n",
    "                else:\n",
    "                    line.append(int(c))\n",
    "            score.append(line)\n",
    "        #for i in range(n):\n",
    "            #visited.add((i, m))\n",
    "        #for j in range(m):\n",
    "            #visited.add((n, j))\n",
    "\n",
    "        queue = [(n-1, m-1)]\n",
    "        record = [[(-1, -1)] * n  for _ in range(n)]\n",
    "        record[n-1][n-1] = (0, 1)\n",
    "        s = 0\n",
    "        mod = 10 ** 9 + 7\n",
    "        for i in range(1, n):\n",
    "            xys = []\n",
    "            y = n - 1 - i\n",
    "            for x in range(n - 1, n - 1 - i, -1):\n",
    "                xys.append((x, y))\n",
    "            x = n - 1 - i\n",
    "            for y in range(n - 1, n - 2 - i, -1):\n",
    "                xys.append((x, y))\n",
    "                        \n",
    "            for x, y in xys:\n",
    "                if score[x][y] != 'X':\n",
    "                    currentMax, num1 = -1, -1\n",
    "                    for x2, y2 in [(x+1, y), (x, y+1), (x+1, y+1)]:\n",
    "                        if x2 < n and y2 < m and score[x2][y2] != 'X' and record[x2][y2] != -1:\n",
    "                            preMax, num2 = record[x2][y2]\n",
    "                            if currentMax == -1 or currentMax < preMax:\n",
    "                                currentMax, num1 = preMax, num2\n",
    "                            elif currentMax == preMax:\n",
    "                                num1 += num2\n",
    "                    if currentMax != -1:\n",
    "                        record[x][y] = (currentMax + score[x][y], num1 % mod)\n",
    "            \n",
    "        if record[0][0] == (-1, -1):\n",
    "            return [0, 0]\n",
    "        else:\n",
    "            return list(record[0][0])\n",
    "'''\n",
    "E 1 1 3 4 5\n",
    "X 4 5 2 X X\n",
    "3 X 4 3 X 4\n",
    "4 4 X 3 1 2\n",
    "2 3 4 5 6 X \n",
    "1 3 4 5 X S\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathsWithMaxScore(self, board: List[str]) -> List[int]:\n",
    "        sum, cnt = 0, 0\n",
    "        m, n = len(board), len(board[0])\n",
    "        mod = 10**9 + 7\n",
    "        f = [[[0] * 2 for _ in range(n)] for _ in range(m)]\n",
    "        for i in range(m - 1, -1, -1):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                if board[i][j] == 'X': continue\n",
    "                v = int(board[i][j]) if board[i][j] != 'S' and board[i][j] != 'E' else 1\n",
    "                if i == m - 1 and j == m - 1:\n",
    "                    f[i][j][0], f[i][j][1] = v, 1\n",
    "                elif i == m - 1:\n",
    "                    if f[i][j + 1][0]:\n",
    "                        f[i][j][0] = f[i][j + 1][0] + v\n",
    "                        f[i][j][1] = 1\n",
    "                elif j == n - 1:\n",
    "                    if f[i+1][j][0]:\n",
    "                        f[i][j][0] = f[i+1][j][0] + v\n",
    "                        f[i][j][1] = 1\n",
    "                else:\n",
    "                    if f[i + 1][j + 1][0]:\n",
    "                        if f[i + 1][j + 1][0] + v > f[i][j][0]:\n",
    "                            f[i][j][0] = f[i + 1][j + 1][0] + v\n",
    "                            f[i][j][1] = f[i + 1][j + 1][1]\n",
    "                        elif f[i + 1][j + 1][0] + v == f[i][j][0]:\n",
    "                            f[i][j][1] += f[i + 1][j + 1][1]\n",
    "                        \n",
    "                    # print(f'i={i},j={j},{f[i][j]}')\n",
    "                    if f[i][j + 1][0]:\n",
    "                        if f[i][j + 1][0] + v > f[i][j][0]:\n",
    "                            f[i][j][0] = f[i][j + 1][0] + v\n",
    "                            f[i][j][1] = f[i][j + 1][1]\n",
    "                        elif f[i][j + 1][0] + v == f[i][j][0]:\n",
    "                            f[i][j][1] += f[i][j + 1][1]\n",
    "                    # print(f'i={i},j={j},{f[i][j]}')\n",
    "                    if f[i + 1][j][0]:\n",
    "                        if f[i + 1][j][0] + v > f[i][j][0]:\n",
    "                            f[i][j][0] = f[i + 1][j][0] + v\n",
    "                            f[i][j][1] = f[i + 1][j][1]\n",
    "                        elif f[i + 1][j][0] + v == f[i][j][0]:\n",
    "                            f[i][j][1] += f[i + 1][j][1]\n",
    "                f[i][j][0] %= mod\n",
    "                f[i][j][1] %= mod\n",
    "                    # print(f'i={i},j={j},{f[i][j]}')\n",
    "        # print(f'{f}')\n",
    "        return [f[0][0][0] - 2, f[0][0][1]] if f[0][0][0] >= 2 else [0,0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathsWithMaxScore(self, board: List[str]) -> List[int]:\n",
    "        n = len(board)\n",
    "        dp = [[[-1, 0] for _ in range(n)] for _ in range(n)]\n",
    "\n",
    "        def update(x: int, y: int, u: int, v: int):\n",
    "            if 0 <= u < n and 0 <= v < n and dp[u][v][0] != -1:\n",
    "                if dp[u][v][0] > dp[x][y][0]:\n",
    "                    dp[x][y] = dp[u][v][:]\n",
    "                elif dp[u][v][0] == dp[x][y][0]:\n",
    "                    dp[x][y][1] += dp[u][v][1]\n",
    "\n",
    "        for i in reversed(range(n)):\n",
    "            for j in reversed(range(n)):\n",
    "                if board[i][j] == \"S\":\n",
    "                    dp[i][j] = [0, 1]\n",
    "                    continue\n",
    "                if board[i][j] == \"X\":\n",
    "                    continue\n",
    "                update(i, j, i + 1, j)   # 下\n",
    "                update(i, j, i, j + 1)   # 右\n",
    "                update(i, j, i + 1, j + 1)   # 右下\n",
    "                # 加上当前节点值\n",
    "                if dp[i][j][0] != -1:\n",
    "                    dp[i][j][0] += (0 if board[i][j] == \"E\" else int(board[i][j]))\n",
    "\n",
    "        max_point, count = dp[0][0]\n",
    "        return [0 if max_point == -1 else max_point, count % (10 ** 9 + 7)]\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathsWithMaxScore(self, board: List[str]) -> List[int]:\n",
    "        n = len(board)\n",
    "        dp = [[[-1,0]]*n for _ in range(n)] # 最大得分、最大次数\n",
    "        dp[n-1][n-1] = [0,1]\n",
    "\n",
    "        def update(x,y,u,v):\n",
    "            if u >= n or v >= n or dp[u][v][0] == -1: # 如果超过边界或者下侧无法到达则无法更新\n",
    "                return\n",
    "            if dp[x][y][0] < dp[u][v][0]:\n",
    "                dp[x][y] = dp[u][v][:]\n",
    "            elif dp[x][y][0] == dp[u][v][0]:\n",
    "                dp[x][y][1] += dp[u][v][1]\n",
    "\n",
    "        for i in range(n-1,-1,-1):\n",
    "            for j in range(n-1,-1,-1):\n",
    "                if not (i == n-1 and j == n-1) and board[i][j] != \"X\":\n",
    "                    update(i,j,i+1,j)\n",
    "                    update(i,j,i,j+1)\n",
    "                    update(i,j,i+1,j+1)\n",
    "                    if dp[i][j][0] != -1:\n",
    "                        dp[i][j][0] += (0 if board[i][j] == \"E\" else ord(board[i][j]) - 48)\n",
    "        return [dp[0][0][0], dp[0][0][1] % (10**9+7)] if dp[0][0][0] != -1 else [0,0]\n",
    "                \n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathsWithMaxScore(self, board: List[str]) -> List[int]:\n",
    "        m, n = len(board), len(board[0])\n",
    "        dp = [[[0, 0] for i in range(m)] + [[-inf, 0]] for j in range(n)] + [[[-inf, 0]] * n]    \n",
    "        dp[m-1][n-1][1] = 1\n",
    "        for i in range(m-1, -1, -1):\n",
    "            for j in range(n-1, -1, -1):\n",
    "                if board[i][j] == 'X':\n",
    "                    dp[i][j][0] = -inf\n",
    "                elif board[i][j] != 'S':\n",
    "                    score, plan = zip(dp[i+1][j], dp[i][j+1], dp[i+1][j+1])\n",
    "                    ma = max(score)\n",
    "                    dp[i][j][0] = ma\n",
    "                    for k in range(3):\n",
    "                        if score[k] == ma:\n",
    "                            dp[i][j][1] += plan[k]\n",
    "                    if board[i][j] != 'E':\n",
    "                        dp[i][j][0] += int(board[i][j])\n",
    "        if dp[0][0][0] < 0:\n",
    "            return [0, 0]\n",
    "        return [dp[0][0][0] % (10**9+7) , dp[0][0][1] % (10**9+7)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathsWithMaxScore(self, board: List[str]) -> List[int]:\n",
    "        n = len(board)\n",
    "        f = [[[-1, 0]] * n for _ in range(n)]\n",
    "\n",
    "        f[-1][-1] = [0, 1]\n",
    "\n",
    "        def update(i, j, x, y):\n",
    "            if x >= n or y >= n or f[x][y] == -1:\n",
    "                return\n",
    "            if f[i][j][0] < f[x][y][0]:\n",
    "                f[i][j] = f[x][y][:]\n",
    "            elif f[i][j][0] == f[x][y][0]:\n",
    "                f[i][j][1] += f[x][y][1]\n",
    "\n",
    "        for i in range(n-1, -1, -1):\n",
    "            for j in range(n-1, -1, -1):\n",
    "                # 首先目标点不能是\"x\",要排除起点\n",
    "                if board[i][j] == \"X\" or ( i == n-1 and j == n-1):\n",
    "                    continue\n",
    "                # 枚举左右两边\n",
    "                update(i, j, i+1, j)\n",
    "                update(i, j, i, j+1)\n",
    "                update(i, j, i+1, j+1)\n",
    "                # 更新后可能不可达，不需要+原位置的值\n",
    "                if f[i][j][0] != -1:\n",
    "                    f[i][j][0] += int(board[i][j]) if board[i][j] != \"E\" else 0\n",
    "        \n",
    "        if f[0][0][0] == -1:\n",
    "            return [0, 0]\n",
    "        else:\n",
    "            return [f[0][0][0], f[0][0][1] % (10 ** 9 + 7)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathsWithMaxScore(self, board: List[str]) -> List[int]:\n",
    "        n = len(board)\n",
    "        dp = [[[0, 0] for _ in range(n)] for _ in range(n)]\n",
    "\n",
    "        for i in reversed(range(n)):\n",
    "            for j in reversed(range(n)):\n",
    "                if board[i][j] == \"S\":\n",
    "                    dp[i][j] = [0, 1]\n",
    "                    continue\n",
    "                if board[i][j] == \"X\":\n",
    "                    dp[i][j] = [0, 0]\n",
    "                    continue\n",
    "                if i < n - 1 and dp[i + 1][j][1] > 0:\n",
    "                    if dp[i + 1][j][0] > dp[i][j][0]:\n",
    "                        dp[i][j] = dp[i + 1][j][:]\n",
    "                    elif dp[i + 1][j][0] == dp[i][j][0]:\n",
    "                        dp[i][j][1] += dp[i + 1][j][1]\n",
    "                if j < n - 1 and dp[i][j + 1][1] > 0:\n",
    "                    if dp[i][j + 1][0] > dp[i][j][0]:\n",
    "                        dp[i][j] = dp[i][j + 1][:]\n",
    "                    elif dp[i][j + 1][0] == dp[i][j][0]:\n",
    "                        dp[i][j][1] += dp[i][j + 1][1]\n",
    "                if i < n - 1 and j < n - 1 and dp[i + 1][j + 1][1] > 0:\n",
    "                    if dp[i + 1][j + 1][0] > dp[i][j][0]:\n",
    "                        dp[i][j] = dp[i + 1][j + 1][:]\n",
    "                    elif dp[i + 1][j + 1][0] == dp[i][j][0]:\n",
    "                        dp[i][j][1] += dp[i + 1][j + 1][1]\n",
    "                if board[i][j] != \"E\" and dp[i][j][1] != 0  :\n",
    "                    dp[i][j][0] += int(board[i][j])\n",
    "         \n",
    "        max_point, count = dp[0][0]\n",
    "        return [max_point, count % (10 ** 9 + 7)]\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathsWithMaxScore(self, board: List[str]) -> List[int]:\n",
    "        m, n = len(board), len(board[0])\n",
    "        dp = [[[-1, 0] for _ in range(n)] for _ in range(m)]\n",
    "        dp[m - 1][n - 1] = [0, 1]\n",
    "        def update(i, j, x, y):\n",
    "            if x >= m or y >= n or dp[x][y][0] == -1:\n",
    "                return\n",
    "            if dp[x][y][0] > dp[i][j][0]:\n",
    "                dp[i][j][0] = dp[x][y][0]\n",
    "                dp[i][j][1] = dp[x][y][1]\n",
    "            elif dp[x][y][0] == dp[i][j][0]:\n",
    "                dp[i][j][1] += dp[x][y][1]\n",
    "\n",
    "        for i in range(m - 1, -1, -1):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                if i == m - 1 and j == n -1 or board[i][j] == 'X': continue\n",
    "                update(i, j, i, j + 1)\n",
    "                update(i, j, i + 1, j)\n",
    "                update(i, j, i + 1, j + 1)\n",
    "                if dp[i][j][0] != -1:\n",
    "                    if board[i][j] == 'E':\n",
    "                        continue\n",
    "                    else:\n",
    "                        dp[i][j][0] += int(board[i][j])\n",
    "        return [dp[0][0][0], dp[0][0][1] % (10 ** 9 + 7)] if dp[0][0][0] != -1 else [0, 0]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathsWithMaxScore(self, board: List[str]) -> List[int]:\n",
    "        n = len(board)\n",
    "        dp = [[[-1, 0]] * n for _ in range(n)]\n",
    "        dp[n - 1][n - 1] = [0, 1]\n",
    "\n",
    "        def update(x, y, u, v):\n",
    "            if u >= n or v >= n or dp[u][v][0] == -1:\n",
    "                return\n",
    "            if dp[u][v][0] > dp[x][y][0]:\n",
    "                dp[x][y] = dp[u][v][:]\n",
    "            elif dp[u][v][0] == dp[x][y][0]:\n",
    "                dp[x][y][1] += dp[u][v][1]\n",
    "\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                if not (i == n - 1 and j == n - 1) and board[i][j] != \"X\":\n",
    "                    update(i, j, i + 1, j)\n",
    "                    update(i, j, i, j + 1)\n",
    "                    update(i, j, i + 1, j + 1)\n",
    "                    if dp[i][j][0] != -1:\n",
    "                        dp[i][j][0] += (0 if board[i][j] == \"E\" else ord(board[i][j]) - 48)\n",
    "        return [dp[0][0][0], dp[0][0][1] % (10**9 + 7)] if dp[0][0][0] != -1 else [0, 0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathsWithMaxScore(self, board: List[str]) -> List[int]:\n",
    "        mod = int(10**9 + 7)\n",
    "\n",
    "        m = len(board)\n",
    "        n = len(board[0])\n",
    "        A = []\n",
    "        for s in board:\n",
    "            row = []\n",
    "            for char in s:\n",
    "                if char in [\"E\", \"S\"]:\n",
    "                    row.append(0)\n",
    "                elif char == \"X\":\n",
    "                    row.append(-1)\n",
    "                else:\n",
    "                    row.append(int(char))\n",
    "            A.append(row)\n",
    "\n",
    "\n",
    "        f = [[[0, 0] for _ in range(n)] for _ in range(m)]\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i == 0 and j == 0:\n",
    "                    f[0][0] = [0, 1]\n",
    "                    continue\n",
    "\n",
    "                left = f[i][j - 1] if (j != 0) else [0, 0]\n",
    "                upper = f[i - 1][j] if (i != 0) else [0, 0]\n",
    "                upper_left = f[i - 1][j - 1] if (i != 0 and j != 0) else [0, 0]\n",
    "\n",
    "                max_path = max(left[0], upper[0], upper_left[0])\n",
    "                path_cnt = 0\n",
    "                if max_path == left[0]:\n",
    "                    path_cnt += left[1]\n",
    "                if max_path == upper[0]:\n",
    "                    path_cnt += upper[1]\n",
    "                if max_path == upper_left[0]:\n",
    "                    path_cnt += upper_left[1]\n",
    "                \n",
    "                if A[i][j] != -1:\n",
    "                    max_path += A[i][j]\n",
    "                    f[i][j] = [max_path, path_cnt % mod]\n",
    "                else:\n",
    "                    f[i][j] = [0, 0]\n",
    "\n",
    "        return f[m - 1][n - 1] if f[m - 1][n - 1][1] != 0 else [0, 0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathsWithMaxScore(self, board: List[str]) -> List[int]:\n",
    "        n = len(board)\n",
    "        f = [[[-1, 0]] * n for _ in range(n)]\n",
    "        f[n-1][n-1] = [0, 1]\n",
    "\n",
    "        def update(i, j, x, y):\n",
    "            if x >= n or y >= n or f[x][y][0] == -1:\n",
    "                return\n",
    "            if f[x][y][0] > f[i][j][0]:\n",
    "                f[i][j] = f[x][y][:]\n",
    "            elif f[x][y][0] == f[i][j][0]:\n",
    "                f[i][j][1] += f[x][y][1]\n",
    "\n",
    "        for i in range(n-1, -1, -1):\n",
    "            for j in range(n-1, -1, -1):\n",
    "                if board[i][j] != 'X' and not (i == n-1 and j == n-1):\n",
    "                    update(i, j, i+1, j)\n",
    "                    update(i, j, i, j + 1)\n",
    "                    update(i, j, i+1, j+1)\n",
    "                    # 再追加当前位置的值\n",
    "                    # 只有当前位置可达的时候，才能加上值\n",
    "                    if f[i][j][0] != -1:\n",
    "                        f[i][j][0] += int(board[i][j] if board[i][j] != \"E\" else 0)\n",
    "        if f[0][0][0] == -1:\n",
    "            return [0, 0]\n",
    "        else:\n",
    "            return [f[0][0][0], f[0][0][1] % (10**9 + 7)]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathsWithMaxScore(self, board: List[str]) -> List[int]:\n",
    "        # dp\n",
    "        n = len(board)\n",
    "        dp = [[[0,0,False] for _ in range(n)] for _ in range(n)]\n",
    "        dp[-1][-1] = [0,1,True]\n",
    "        \n",
    "        for i in range(n - 2, -1 ,-1):\n",
    "            if dp[i + 1][-1][2] and not board[i][-1] == 'X':\n",
    "               dp[i][-1] = [dp[i + 1][-1][0] + int(board[i][-1]), 1, True]\n",
    "        for i in range(n - 2, -1 , -1):\n",
    "            if dp[-1][i + 1][2] and not board[-1][i] =='X':\n",
    "                dp[-1][i] = [dp[-1][i + 1][0] + int(board[-1][i]), 1, True]\n",
    " \n",
    "        for i in range(n - 2, -1, -1):\n",
    "            for j in range(n - 2, -1, -1):\n",
    "                if board[i][j] == 'X':\n",
    "                    continue\n",
    "                flag =False\n",
    "                for a, b in [[i + 1, j], [i, j + 1], [i + 1, j + 1]]:\n",
    "                    if dp[a][b][2]:\n",
    "                        flag = True\n",
    "                        if dp[i][j][0] < dp[a][b][0]:\n",
    "                            dp[i][j] = dp[a][b][:]\n",
    "                        elif dp[i][j][0] == dp[a][b][0]:\n",
    "                            dp[i][j][1] += dp[a][b][1]\n",
    "\n",
    "\n",
    "                #part 1\n",
    "                dp[i][j] = [dp[i][j][0] + int(board[i][j]) if not board[i][j]=='E' else dp[i][j][0], dp[i][j][1] % int(1e9 + 7), flag]\n",
    "                \n",
    "                #part 2\n",
    "                # dp[i][j][0] += int(board[i][j]) if not board[i][j]=='E' else 0\n",
    "                # dp[i][j][1] %= int(1e9 + 7)\n",
    "                # dp[i][j][2] = flag\n",
    "\n",
    "\n",
    "        return [dp[0][0][0],dp[0][0][1]% int(1e9 + 7)]\n",
    "                \n",
    "\n",
    "        # dfs超时了 这里不支持@cache \n",
    "        # r, c = len(board), len(board[0])\n",
    "        # mp = defaultdict(int)\n",
    "        # ans = -1\n",
    "        # def dfs(row: int, column: int, v: int) -> None:\n",
    "        #     nonlocal ans\n",
    "        #     if row == 0 and column == 0:\n",
    "        #         mp[v] += 1\n",
    "        #         ans = max(ans, v)\n",
    "        #         return\n",
    "        #     for a, b in [(row - 1, column), (row, column - 1), (row - 1, column - 1)]:\n",
    "        #         if not 0 <= a < r or not 0 <= b < c or board[a][b] == 'X':\n",
    "        #             continue\n",
    "        #         dfs(a, b, v if board[a][b]==\"E\" else v + int(board[a][b]))\n",
    "        # dfs(r - 1 ,c - 1, 0)\n",
    "        # return [ans, mp[ans] % int(10e9 + 7)] if ans >= 0 else [0 ,0]\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathsWithMaxScore(self, board: List[str]) -> List[int]:\n",
    "        mod = 10**9+7\n",
    "        # 动态规划\n",
    "        # dp[i][j]表示从S出发到达(i,j)，得分的最大值，最大得分的方案数\n",
    "        def update(x,y,u,v):\n",
    "            if u >=n or v >= n or dp[u][v][0] == -1:\n",
    "                return\n",
    "            if dp[u][v][0] > dp[x][y][0]:\n",
    "                dp[x][y] = dp[u][v][:]\n",
    "            elif dp[u][v][0] == dp[x][y][0]:\n",
    "                dp[x][y][1] += dp[u][v][1]\n",
    "\n",
    "        n = len(board)\n",
    "        dp = [[[-1,0]]*n for _ in range(n)]\n",
    "        dp[n-1][n-1] = [0,1]\n",
    "        for i in range(n-1,-1,-1):\n",
    "            for j in range(n-1,-1,-1):\n",
    "                if not(i == n-1 and j == n-1) and board[i][j] != 'X':\n",
    "                    update(i,j,i+1,j)\n",
    "                    update(i,j,i,j+1)\n",
    "                    update(i,j,i+1,j+1)\n",
    "                    if dp[i][j][0] != -1:\n",
    "                        dp[i][j][0] += (0 if board[i][j] == 'E' else int(board[i][j]))\n",
    "        return [dp[0][0][0],dp[0][0][1]%mod] if dp[0][0][0] != -1 else [0,0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathsWithMaxScore(self, board: List[str]) -> List[int]:\n",
    "        n = len(board)\n",
    "        dp = [[[-1, 0]] * n for _ in range(n)]\n",
    "        dp[n - 1][n - 1] = [0, 1]\n",
    "\n",
    "        def update(x, y, u, v):\n",
    "            if u >= n or v >= n or dp[u][v][0] == -1:\n",
    "                return\n",
    "            if dp[u][v][0] > dp[x][y][0]:\n",
    "                dp[x][y] = dp[u][v][:]\n",
    "            elif dp[u][v][0] == dp[x][y][0]:\n",
    "                dp[x][y][1] += dp[u][v][1]\n",
    "\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                if not (i == n - 1 and j == n - 1) and board[i][j] != \"X\":\n",
    "                    update(i, j, i + 1, j)\n",
    "                    update(i, j, i, j + 1)\n",
    "                    update(i, j, i + 1, j + 1)\n",
    "                    if dp[i][j][0] != -1:\n",
    "                        dp[i][j][0] += (0 if board[i][j] == \"E\" else ord(board[i][j]) - 48)\n",
    "        return [dp[0][0][0], dp[0][0][1] % (10**9 + 7)] if dp[0][0][0] != -1 else [0, 0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathsWithMaxScore(self, board: List[str]) -> List[int]:\n",
    "        n = len(board)\n",
    "        dp = [[[-1, 0]] * n for _ in range(n)]\n",
    "        dp[n - 1][n - 1] = [0, 1]\n",
    "\n",
    "        def update(x, y, u, v):\n",
    "            if u >= n or v >= n or dp[u][v][0] == -1:\n",
    "                return\n",
    "            if dp[u][v][0] > dp[x][y][0]:\n",
    "                dp[x][y] = dp[u][v][:]\n",
    "            elif dp[u][v][0] == dp[x][y][0]:\n",
    "                dp[x][y][1] += dp[u][v][1]\n",
    "\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                if not (i == n - 1 and j == n - 1) and board[i][j] != \"X\":\n",
    "                    update(i, j, i + 1, j)\n",
    "                    update(i, j, i, j + 1)\n",
    "                    update(i, j, i + 1, j + 1)\n",
    "                    if dp[i][j][0] != -1:\n",
    "                        dp[i][j][0] += (0 if board[i][j] == \"E\" else ord(board[i][j]) - 48)\n",
    "        return [dp[0][0][0], dp[0][0][1] % (10**9 + 7)] if dp[0][0][0] != -1 else [0, 0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathsWithMaxScore(self, board: List[str]) -> List[int]:\n",
    "        # dp\n",
    "        r, c = len(board), len(board[0])\n",
    "        dp = [[[0,0,False] for _ in range(c)] for _ in range(r)]\n",
    "        dp[-1][-1] = [0,1,True]\n",
    "        for i in range(r - 2, -1 ,-1):\n",
    "            if dp[i + 1][-1][2] and not board[i][-1] == 'X':\n",
    "               dp[i][-1] = [dp[i + 1][-1][0] + int(board[i][-1]), 1, True]\n",
    "        for i in range(c - 2, -1 , -1):\n",
    "            if dp[-1][i + 1][2] and not board[-1][i] =='X':\n",
    "                dp[-1][i] = [dp[-1][i + 1][0] + int(board[-1][i]), 1, True]\n",
    "        for i in range(r - 2, -1, -1):\n",
    "            for j in range(c - 2, -1, -1):\n",
    "                if board[i][j] == 'X':\n",
    "                    continue\n",
    "                flag =False\n",
    "                for a, b in [[i + 1, j], [i, j + 1], [i + 1, j + 1]]:\n",
    "                    if dp[a][b][2]:\n",
    "                        flag = True\n",
    "                        if dp[i][j][0] < dp[a][b][0]:\n",
    "                            dp[i][j] = dp[a][b]\n",
    "                        elif dp[i][j][0] == dp[a][b][0]:\n",
    "                            dp[i][j][1] += dp[a][b][1]\n",
    "                dp[i][j] = [dp[i][j][0] + int(board[i][j]) if not board[i][j]=='E' else dp[i][j][0], dp[i][j][1] % int(10**9 + 7), flag]\n",
    "                # if not board[i][j]=='E':\n",
    "                #     dp[i][j][0] += int(board[i][j]) \n",
    "                # dp[i][j][1] %= int(10e9 + 7)\n",
    "                # dp[i][j][2] = flag\n",
    "        return [dp[0][0][0],dp[0][0][1]% int(10**9 + 7)]\n",
    "                \n",
    "                 \n",
    "        # return [0,0]\n",
    "\n",
    "\n",
    "        # dfs超时了 这里不支持@cache \n",
    "        # r, c = len(board), len(board[0])\n",
    "        # mp = defaultdict(int)\n",
    "        # ans = -1\n",
    "        # def dfs(row: int, column: int, v: int) -> None:\n",
    "        #     nonlocal ans\n",
    "        #     if row == 0 and column == 0:\n",
    "        #         mp[v] += 1\n",
    "        #         ans = max(ans, v)\n",
    "        #         return\n",
    "        #     for a, b in [(row - 1, column), (row, column - 1), (row - 1, column - 1)]:\n",
    "        #         if not 0 <= a < r or not 0 <= b < c or board[a][b] == 'X':\n",
    "        #             continue\n",
    "        #         dfs(a, b, v if board[a][b]==\"E\" else v + int(board[a][b]))\n",
    "        # dfs(r - 1 ,c - 1, 0)\n",
    "        # return [ans, mp[ans] % int(10e9 + 7)] if ans >= 0 else [0 ,0]\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathsWithMaxScore(self, board: List[str]) -> List[int]:\n",
    "        size = len(board)\n",
    "        point = [[0] * size for _ in range(size)]\n",
    "        path = [[0] * size for _ in range(size)]\n",
    "\n",
    "        for i in range(size - 1, -1, -1):\n",
    "            for j in range(size - 1, -1, -1):\n",
    "                if board[i][j] == 'S':\n",
    "                    point[i][j] = 0\n",
    "                    path[i][j] = 1\n",
    "                    continue\n",
    "                if board[i][j] == 'X':\n",
    "                    point[i][j] = 0\n",
    "                    path[i][j] = 0\n",
    "                    continue\n",
    "                cur = 0 if board[i][j] == 'E' else int(board[i][j]) \n",
    "                if (i + 1) < size and path[i + 1][j] != 0:\n",
    "                    if point[i + 1][j] + cur == point[i][j]:\n",
    "                        path[i][j] += path[i + 1][j]\n",
    "                    if point[i + 1][j] + cur > point[i][j]:\n",
    "                        path[i][j] = path[i + 1][j]\n",
    "                        point[i][j] = point[i + 1][j] + cur\n",
    "                if (j + 1) < size and path[i][j + 1] != 0:\n",
    "                    if point[i][j + 1] + cur == point[i][j]:\n",
    "                        path[i][j] += path[i][j + 1]\n",
    "                    if point[i][j + 1] + cur > point[i][j]:\n",
    "                        path[i][j] = path[i][j + 1]\n",
    "                        point[i][j] = point[i][j + 1] + cur\n",
    "                if (i + 1) < size and (j + 1) < size and path[i + 1][j + 1] != 0:\n",
    "                    if point[i + 1][j + 1] + cur == point[i][j]:\n",
    "                        path[i][j] += path[i + 1][j + 1]\n",
    "                    if point[i + 1][j + 1] + cur > point[i][j]:\n",
    "                        path[i][j] = path[i + 1][j + 1]\n",
    "                        point[i][j] = point[i + 1][j + 1] + cur\n",
    "        \n",
    "        print(path)\n",
    "        print(point)\n",
    "        return [point[0][0] % (10 ** 9 + 7), path[0][0] % (10 ** 9 + 7)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathsWithMaxScore(self, board: List[str]) -> List[int]:\n",
    "        n=len(board)\n",
    "        dp=[[[-1,0]]*n for _ in range(n)]\n",
    "        dp[n-1][n-1]=[0,1]\n",
    "#[分数,线路数]\n",
    "\n",
    "#u存储分数,v存储线路数\n",
    "        def update(i:int, j:int , u:int ,v:int):\n",
    "            if u>=n or v>=n or dp[u][v][0]==-1:\n",
    "                return \n",
    "            if dp[i][j][0]<dp[u][v][0]:\n",
    "                dp[i][j]=dp[u][v][:]\n",
    "                \n",
    "            elif dp[i][j][0]==dp[u][v][0]:\n",
    "                dp[i][j][1]+=dp[u][v][1]\n",
    "\n",
    "        for i in range(n-1,-1,-1):\n",
    "            for j in range(n-1,-1,-1):\n",
    "                if not (i==n-1 and j==n-1) and board[i][j]!=\"X\":\n",
    "                    update(i,j,i+1,j)\n",
    "                    update(i,j,i,j+1)\n",
    "                    update(i,j,i+1,j+1)\n",
    "                    if dp[i][j][0]!=-1:\n",
    "                        dp[i][j][0]+= (0 if board[i][j]==\"E\"else int(board[i][j]))\n",
    "\n",
    "\n",
    "        return [dp[0][0][0]%(10**9+7),dp[0][0][1]%(10**9+7)] if dp[0][0][0]!=-1 else [0,0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "dp = [[[0] * 2 for __ in range(100)] for _ in range(100)]\n",
    "class Solution:\n",
    "    def pathsWithMaxScore(self, board: List[str]) -> List[int]:\n",
    "        n = len(board)\n",
    "        dp[n - 1][n - 1][0] = 0\n",
    "        dp[n - 1][n - 1][1] = 1\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            if dp[i + 1][n - 1][0] == -1 or board[i][n - 1] == \"X\":\n",
    "                dp[i][n - 1][0] = -1\n",
    "            else:\n",
    "                dp[i][n - 1][0] = dp[i + 1][n - 1][0] + ord(board[i][n - 1]) - 48\n",
    "            dp[i][n - 1][1] = dp[i + 1][n - 1][1]\n",
    "        for j in range(n - 2, -1, -1):\n",
    "            if dp[n - 1][j + 1][0] == -1 or board[n - 1][j] == \"X\":\n",
    "                dp[n - 1][j][0] = -1\n",
    "            else:\n",
    "                dp[n - 1][j][0] = dp[n - 1][j + 1][0] + ord(board[n - 1][j]) - 48\n",
    "            dp[n - 1][j][1] = dp[n - 1][j + 1][1]\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            for j in range(n - 2, -1, -1):\n",
    "                if board[i][j] == \"X\":\n",
    "                    dp[i][j][0] = -1\n",
    "                else:\n",
    "                    dp[i][j][0] = max(dp[i + 1][j][0], dp[i][j + 1][0], dp[i + 1][j + 1][0])\n",
    "                if dp[i][j][0] != -1:\n",
    "                    dp[i][j][1] = 0\n",
    "                    if dp[i][j][0] == dp[i + 1][j][0]:\n",
    "                        dp[i][j][1] += dp[i + 1][j][1]\n",
    "                    if dp[i][j][0] == dp[i][j + 1][0]:\n",
    "                        dp[i][j][1] += dp[i][j + 1][1]\n",
    "                    if dp[i][j][0] == dp[i + 1][j + 1][0]:\n",
    "                        dp[i][j][1] += dp[i + 1][j + 1][1]\n",
    "                    dp[i][j][0] += 0 if board[i][j] == \"E\" else (ord(board[i][j]) - 48)\n",
    "        if dp[0][0][0] == -1:\n",
    "            return [0, 0]\n",
    "\n",
    "        return [dp[0][0][0] % 1000000007, dp[0][0][1] % 1000000007]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathsWithMaxScore(self, board: List[str]) -> List[int]:\n",
    "        n = len(board)\n",
    "        MOD = 10**9+7\n",
    "        dp = [[[-inf, -inf] for _ in range(n)] for _ in range(n)]\n",
    "        for x in range(n):\n",
    "            for y in range(n):\n",
    "                if x == 0 and y == 0:\n",
    "                    dp[x][y] = [0, 1]\n",
    "                    continue\n",
    "                if board[x][y] == 'X':\n",
    "                    continue\n",
    "                res = [[-inf, -inf] for _ in range(3)]\n",
    "                plus = 0 if board[x][y] == 'S' else int(board[x][y])\n",
    "                if x > 0:\n",
    "                    res[0][0] = dp[x-1][y][0] + plus\n",
    "                    res[0][1] = dp[x-1][y][1]\n",
    "                if y > 0:\n",
    "                    res[1][0] = dp[x][y-1][0] + plus\n",
    "                    res[1][1] = dp[x][y-1][1]\n",
    "                if x > 0 and y > 0:\n",
    "                    res[2][0] = dp[x-1][y-1][0] + plus\n",
    "                    res[2][1] = dp[x-1][y-1][1]\n",
    "                dp[x][y] = [max(res[0][0], res[1][0], res[2][0]), 0]\n",
    "                for i in range(3):\n",
    "                    if res[i][0] == dp[x][y][0]:\n",
    "                        dp[x][y][1] += res[i][1]\n",
    "        if dp[-1][-1] == [-inf, -inf]:\n",
    "            return [0, 0]\n",
    "        return [dp[-1][-1][0], dp[-1][-1][1]%MOD]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathsWithMaxScore(self, board: List[str]) -> List[int]:\n",
    "        n = len(board)\n",
    "        board[0] = '0' + board[0][1:]\n",
    "        Mod = 10**9+7\n",
    "        d= [[ [-inf , 0] for _ in range(n+1)] for _ in range(n+1)]\n",
    "        d[n-1][n-1]=[0,1]\n",
    "        for i in range(n-1,-1,-1):\n",
    "            for j in range(n-1, -1, -1):\n",
    "                if board[i][j] == \"S\":\n",
    "                    continue\n",
    "                if board[i][j] == \"X\":\n",
    "                    continue\n",
    "                v, c = d[i][j]\n",
    "                for x, y in [d[i][j+1], d[i+1][j], d[i+1][j+1]]:\n",
    "                    if x > v:\n",
    "                        v = x\n",
    "                        c = y\n",
    "                    elif x == v:\n",
    "                        c += y\n",
    "                d[i][j][0] = v + int(board[i][j])\n",
    "                d[i][j][1] = c%Mod\n",
    "        if d[0][0][0]==-inf:\n",
    "            return [0,0]\n",
    "        return d[0][0]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathsWithMaxScore(self, board: List[str]) -> List[int]:\n",
    "        m, n = len(board), len(board[0])\n",
    "        has = [[[float(\"-inf\"), 0] for i in range(n+1)] for j in range(m+1)]\n",
    "        has[m-1][n-1] = [0, 1]\n",
    "        for i in range(m-1, -1, -1):\n",
    "            for j in range(n-1, -1, -1):\n",
    "                v = board[i][j]\n",
    "                if v not in \"XS\":\n",
    "                    v = 0 if v == \"E\" else int(v)\n",
    "                    a, b = float(\"-inf\"), 0\n",
    "                    for x, y in [has[i+1][j], has[i][j+1], has[i+1][j+1]]:\n",
    "                        if x > a:\n",
    "                            a, b = x, y\n",
    "                        elif x == a:\n",
    "                            b = (b+y) % 1000000007\n",
    "                    has[i][j] = [a+v, b]\n",
    "        return [0, 0] if has[0][0][0] == float(\"-inf\") else has[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathsWithMaxScore(self, board: List[str]) -> List[int]:\n",
    "        n = len(board)\n",
    "        MOD = 10**9+7\n",
    "        dp = [[[-inf, -inf] for _ in range(n)] for _ in range(n)]\n",
    "        for x in range(n):\n",
    "            for y in range(n):\n",
    "                if x == 0 and y == 0:\n",
    "                    dp[x][y] = [0, 1]\n",
    "                    continue\n",
    "                if board[x][y] == 'X':\n",
    "                    continue\n",
    "                res = [[-inf, -inf] for _ in range(3)]\n",
    "                plus = 0 if board[x][y] == 'S' else int(board[x][y])\n",
    "                if x > 0:\n",
    "                    res[0][0] = dp[x-1][y][0] + plus\n",
    "                    res[0][1] = dp[x-1][y][1]\n",
    "                if y > 0:\n",
    "                    res[1][0] = dp[x][y-1][0] + plus\n",
    "                    res[1][1] = dp[x][y-1][1]\n",
    "                if x > 0 and y > 0:\n",
    "                    res[2][0] = dp[x-1][y-1][0] + plus\n",
    "                    res[2][1] = dp[x-1][y-1][1]\n",
    "                dp[x][y] = [max(res[0][0], res[1][0], res[2][0]), 0]\n",
    "                for i in range(3):\n",
    "                    if res[i][0] == dp[x][y][0]:\n",
    "                        dp[x][y][1] += res[i][1]\n",
    "        if dp[-1][-1] == [-inf, -inf]:\n",
    "            return [0, 0]\n",
    "        return [dp[-1][-1][0], dp[-1][-1][1]%MOD]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathsWithMaxScore(self, board: List[str]) -> List[int]:\n",
    "        dp = [[0 for i in range(len(board[0]))] for j in range(len(board))]\n",
    "        if board[0][1]!='X':\n",
    "            dp[0][1] = [int(board[0][1]),1]\n",
    "        else:dp[0][1]=[0,0]\n",
    "        if board[1][0]!='X':\n",
    "            dp[1][0] = [int(board[1][0]),1]\n",
    "        else:dp[1][0] = [0, 0]\n",
    "        if board[1][1]!='X':\n",
    "            if board[1][1]=='S':\n",
    "                cu = 0\n",
    "            else:cu = int(board[1][1])\n",
    "            dp[1][1] = [cu+max(dp[1][0][0],dp[0][1][0])]\n",
    "            if dp[1][0][0]==dp[0][1][0] and dp[1][0][0]!=0:\n",
    "                dp[1][1].append(2)\n",
    "            else:dp[1][1].append(1)\n",
    "        elif board[1][1]=='X':\n",
    "            dp[1][1]=[0,0]\n",
    "        dp[0][0] = [0, 1]\n",
    "        for i in range(len(dp)):\n",
    "            for j in range(len(dp[0])):\n",
    "                if i <= 1 and j <= 1: continue\n",
    "                if i==0:\n",
    "                    if board[i][j]!='X':\n",
    "                        dp[i][j]=[int(board[i][j])+dp[i][j-1][0],dp[i][j-1][1]]\n",
    "                    else:dp[i][j]=[0,0]\n",
    "                elif j==0:\n",
    "                    if board[i][j]!='X':\n",
    "                        dp[i][j]=[int(board[i][j])+dp[i-1][j][0],dp[i-1][j][1]]\n",
    "                    else:dp[i][j]=[0,0]\n",
    "                else:\n",
    "\n",
    "                    if board[i][j] != 'X':\n",
    "                        if board[i][j]=='S':\n",
    "                            cu = 0\n",
    "                        else:cu = int(board[i][j])\n",
    "                        ma = max(dp[i-1][j][0],dp[i][j-1][0],dp[i-1][j-1][0])\n",
    "                        dp[i][j] = [cu+ma]\n",
    "                        dp[i][j].append(0)\n",
    "                        if dp[i-1][j][0]==ma:\n",
    "                            dp[i][j][1]+=dp[i-1][j][1]\n",
    "                        if dp[i][j-1][0]==ma:\n",
    "                            dp[i][j][1]+=dp[i][j-1][1]\n",
    "                        if dp[i-1][j-1][0]==ma:\n",
    "                            dp[i][j][1]+=dp[i-1][j-1][1]\n",
    "                    else:dp[i][j] =[0,0]\n",
    "        if dp[-1][-1][1]!=0:\n",
    "            return [dp[-1][-1][0]%1000000007,dp[-1][-1][1]%1000000007]\n",
    "        else:return [0,0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathsWithMaxScore(self, board: List[str]) -> List[int]:\n",
    "        n = len(board)\n",
    "        dp = [[[0, 0] for _ in range(n)] for _ in range(n)]\n",
    "\n",
    "        for i in reversed(range(n)):\n",
    "            for j in reversed(range(n)):\n",
    "                if board[i][j] == \"S\":\n",
    "                    dp[i][j] = [0, 1]\n",
    "                    continue\n",
    "                if board[i][j] == \"X\":\n",
    "                    dp[i][j] = [0, 0]\n",
    "                    continue\n",
    "                if i < n - 1 and dp[i + 1][j][1] > 0:\n",
    "                    if dp[i + 1][j][0] > dp[i][j][0]:\n",
    "                        dp[i][j] = dp[i + 1][j][:]\n",
    "                    elif dp[i + 1][j][0] == dp[i][j][0]:\n",
    "                        dp[i][j][1] += dp[i + 1][j][1]\n",
    "                if j < n - 1 and dp[i][j + 1][1] > 0:\n",
    "                    if dp[i][j + 1][0] > dp[i][j][0]:\n",
    "                        dp[i][j] = dp[i][j + 1][:]\n",
    "                    elif dp[i][j + 1][0] == dp[i][j][0]:\n",
    "                        dp[i][j][1] += dp[i][j + 1][1]\n",
    "                if i < n - 1 and j < n - 1 and dp[i + 1][j + 1][1] > 0:\n",
    "                    if dp[i + 1][j + 1][0] > dp[i][j][0]:\n",
    "                        dp[i][j] = dp[i + 1][j + 1][:]\n",
    "                    elif dp[i + 1][j + 1][0] == dp[i][j][0]:\n",
    "                        dp[i][j][1] += dp[i + 1][j + 1][1]\n",
    "                if board[i][j] != \"E\" and dp[i][j][1] != 0  :\n",
    "                    dp[i][j][0] += int(board[i][j])\n",
    "         \n",
    "        print(dp)\n",
    "        max_point, count = dp[0][0]\n",
    "        return [max_point, count % (10 ** 9 + 7)]\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathsWithMaxScore(self, board: List[str]) -> List[int]:\n",
    "        score = []\n",
    "        n, m = len(board), len(board[0])\n",
    "        visited = set((n-1, m-1))\n",
    "        for i in range(n):\n",
    "            line = []\n",
    "            for j in range(m):\n",
    "                c = board[i][j]\n",
    "                if c == 'X':\n",
    "                    line.append('X')\n",
    "                    visited.add((i, j))\n",
    "                elif c == 'E':\n",
    "                    line.append(0)\n",
    "                elif c == 'S':\n",
    "                    line.append('S')\n",
    "                else:\n",
    "                    line.append(int(c))\n",
    "            score.append(line)\n",
    "        #for i in range(n):\n",
    "            #visited.add((i, m))\n",
    "        #for j in range(m):\n",
    "            #visited.add((n, j))\n",
    "\n",
    "        queue = [(n-1, m-1)]\n",
    "        record = {(n-1, n-1):(0, 1)}\n",
    "        s = 0\n",
    "        mod = 10 ** 9 + 7\n",
    "        for i in range(1, n):\n",
    "            xys = []\n",
    "            y = n - 1 - i\n",
    "            for x in range(n - 1, n - 1 - i, -1):\n",
    "                xys.append((x, y))\n",
    "            x = n - 1 - i\n",
    "            for y in range(n - 1, n - 2 - i, -1):\n",
    "                xys.append((x, y))\n",
    "                        \n",
    "            for x, y in xys:\n",
    "                if score[x][y] != 'X':\n",
    "                    currentMax, num1 = -1, -1\n",
    "                    for x2, y2 in [(x+1, y), (x, y+1), (x+1, y+1)]:\n",
    "                        if x2 < n and y2 < m and score[x2][y2] != 'X' and (x2, y2) in record:\n",
    "                            preMax, num2 = record[(x2, y2)]\n",
    "                            if currentMax == -1 or currentMax < preMax:\n",
    "                                currentMax, num1 = preMax, num2\n",
    "                            elif currentMax == preMax:\n",
    "                                num1 += num2\n",
    "                    if currentMax != -1:\n",
    "                        record[(x, y)] = (currentMax + score[x][y], num1 % mod)\n",
    "            \n",
    "        if (0, 0) not in record:\n",
    "            return [0, 0]\n",
    "        else:\n",
    "            return list(record[(0, 0)])\n",
    "'''\n",
    "E 1 1 3 4 5\n",
    "X 4 5 2 X X\n",
    "3 X 4 3 X 4\n",
    "4 4 X 3 1 2\n",
    "2 3 4 5 6 X \n",
    "1 3 4 5 X S\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathsWithMaxScore(self, board: List[str]) -> List[int]:\n",
    "        m,n=len(board),len(board[0])\n",
    "        cache= [[-1 for _ in range(n+1)] for _ in range(m+1)]\n",
    "        max_score, new_cache = self.dp(board,cache, m,n)\n",
    "        # print(new_cache)\n",
    "        ch=new_cache\n",
    "        visited=[[-1 for _ in range(n+1)] for _ in range(m+1)]\n",
    "        \n",
    "        def dfs(i, j):\n",
    "            if i==m-1 and j==n-1:\n",
    "                return 1\n",
    "            if i==m or j==n:\n",
    "                return 0\n",
    "            if visited[i][j]>=0:\n",
    "                return visited[i][j]\n",
    "            if ch[i][j]<0 :\n",
    "                visited[i][j] = 1\n",
    "                return 0\n",
    "            max_score=max(ch[i][j+1], ch[i+1][j],ch[i+1][j+1])\n",
    "            num_paths=0\n",
    "            if max_score==ch[i][j+1]:\n",
    "                num_paths+=dfs(i,j+1)% (10**9+7)\n",
    "            if max_score==ch[i+1][j]:\n",
    "                num_paths+=dfs(i+1,j)% (10**9+7)\n",
    "            if max_score==ch[i+1][j+1]:\n",
    "                num_paths+=dfs(i+1,j+1)% (10**9+7)\n",
    "                # print(i,j,num_paths)\n",
    "            num_paths%=(10**9+7)\n",
    "            visited[i][j] = num_paths\n",
    "            return num_paths     \n",
    "\n",
    "        # num_paths=dfs(0, 0, new_cache)\n",
    "        num_paths=dfs(0, 0)\n",
    "        # print(max_score, num_paths)\n",
    "        return [max_score if max_score>=0 else 0, num_paths]\n",
    "\n",
    "    def dp(self, bd, ch, m, n):\n",
    "\n",
    "        for i in range(m-1, -1, -1):\n",
    "            for j in range(n-1, -1, -1):\n",
    "                if bd[i][j] in ['X']:\n",
    "                    ch[i][j]=-1\n",
    "                    continue\n",
    "                if bd[i][j] in ['S']:\n",
    "                    ch[i][j]=0\n",
    "                else:\n",
    "                    cur_num=int(bd[i][j]) if bd[i][j].isdigit() else 0\n",
    "                    max_cur=max( ch[i+1][j], ch[i][j+1], ch[i+1][j+1])\n",
    "                    \n",
    "                    ch[i][j] = (max_cur+cur_num)% (10**9+7) if max_cur>=0 else -1\n",
    "                \n",
    "        return ch[0][0], ch"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathsWithMaxScore(self, board: List[str]) -> List[int]:\n",
    "        n=len(board)\n",
    "        MOD=10**9 + 7\n",
    "        self.dps = [[-inf for _ in range(n)] for _ in range(n)]\n",
    "        self.dpn = [[0 for _ in range(n)] for _ in range(n)]\n",
    "        self.visited = [[False for _ in range(n)] for _ in range(n)]\n",
    "        self.dps[n-1][n-1]=0\n",
    "        self.dpn[n-1][n-1]=1\n",
    "        def dfs(x, y):\n",
    "            if self.visited[x][y]: return\n",
    "            if board[x][y] in ['S','X']:\n",
    "                self.visited[x][y]=True\n",
    "                return\n",
    "            s=int(board[x][y]) if board[x][y]!='E' else 0\n",
    "            s1,s2,s3,n1,n2,n3=-inf,-inf,-inf,0,0,0\n",
    "            temp=0\n",
    "            if x+1<n and self.dps[x+1][y]!='X':\n",
    "                dfs(x+1,y)\n",
    "                s1,n1 = self.dps[x+1][y],self.dpn[x+1][y]\n",
    "            if y+1<n and self.dps[x][y+1]!='X':\n",
    "                dfs(x,y+1)\n",
    "                s2,n2 = self.dps[x][y+1],self.dpn[x][y+1]\n",
    "            if x+1<n and y+1<n and self.dps[x+1][y+1]!='X':\n",
    "                dfs(x+1,y+1)\n",
    "                s3,n3 = self.dps[x+1][y+1],self.dpn[x+1][y+1]\n",
    "            if s1==max(s1,s2,s3):\n",
    "                temp += n1\n",
    "            if s2==max(s1,s2,s3):\n",
    "                temp += n2\n",
    "            if s3==max(s1,s2,s3):\n",
    "                temp += n3\n",
    "            self.dps[x][y] = max(s1,s2,s3)+s\n",
    "            self.dpn[x][y] = temp % MOD\n",
    "            self.visited[x][y]=True\n",
    "        for i in range(n):\n",
    "            for k in range(i): dfs(n-1-i,n-1-k)\n",
    "            for k in range(i): dfs(n-1-k,n-1-i)\n",
    "            dfs(n-1-i,n-1-i)\n",
    "        # dfs(0,0)\n",
    "        # print(self.dps, self.dpn)\n",
    "        return [self.dps[0][0] if self.dps[0][0]!=-inf else 0, self.dpn[0][0]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathsWithMaxScore(self, board: List[str]) -> List[int]:\n",
    "        n=len(board)\n",
    "        MOD=10**9 + 7\n",
    "        self.dps = [[-inf for _ in range(n)] for _ in range(n)]\n",
    "        self.dpn = [[0 for _ in range(n)] for _ in range(n)]\n",
    "        self.visited = [[False for _ in range(n)] for _ in range(n)]\n",
    "        self.dps[n-1][n-1]=0\n",
    "        self.dpn[n-1][n-1]=1\n",
    "        def dfs(x, y):\n",
    "            if self.visited[x][y]: return\n",
    "            if board[x][y] in ['S','X']:\n",
    "                self.visited[x][y]=True\n",
    "                return\n",
    "            s=int(board[x][y]) if board[x][y]!='E' else 0\n",
    "            s1,s2,s3,n1,n2,n3=-inf,-inf,-inf,0,0,0\n",
    "            temp=0\n",
    "            if x+1<n and self.dps[x+1][y]!='X':\n",
    "                dfs(x+1,y)\n",
    "                s1,n1 = self.dps[x+1][y],self.dpn[x+1][y]\n",
    "            if y+1<n and self.dps[x][y+1]!='X':\n",
    "                dfs(x,y+1)\n",
    "                s2,n2 = self.dps[x][y+1],self.dpn[x][y+1]\n",
    "            if x+1<n and y+1<n and self.dps[x+1][y+1]!='X':\n",
    "                dfs(x+1,y+1)\n",
    "                s3,n3 = self.dps[x+1][y+1],self.dpn[x+1][y+1]\n",
    "            if s1==max(s1,s2,s3):\n",
    "                temp += n1\n",
    "            if s2==max(s1,s2,s3):\n",
    "                temp += n2\n",
    "            if s3==max(s1,s2,s3):\n",
    "                temp += n3\n",
    "            self.dps[x][y] = max(s1,s2,s3)+s\n",
    "            self.dpn[x][y] = temp % MOD\n",
    "            self.visited[x][y]=True\n",
    "        for i in range(n):\n",
    "            for k in range(i): dfs(n-1-i,n-1-k)\n",
    "            for k in range(i): dfs(n-1-k,n-1-i)\n",
    "            dfs(n-1-i,n-1-i)\n",
    "        # dfs(0,0)\n",
    "        # print(self.dps, self.dpn)\n",
    "        return [self.dps[0][0] if self.dps[0][0]!=-inf else 0, self.dpn[0][0]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathsWithMaxScore(self, board: List[str]) -> List[int]:\n",
    "        n=len(board)\n",
    "        MOD=10**9 + 7\n",
    "        self.dps = [[-inf for _ in range(n)] for _ in range(n)]\n",
    "        self.dpn = [[0 for _ in range(n)] for _ in range(n)]\n",
    "        self.visited = [[False for _ in range(n)] for _ in range(n)]\n",
    "        self.dps[n-1][n-1]=0\n",
    "        self.dpn[n-1][n-1]=1\n",
    "        def dfs(x, y):\n",
    "            if self.visited[x][y]: return\n",
    "            if board[x][y] in ['S','X']:\n",
    "                self.visited[x][y]=True\n",
    "                return\n",
    "            s=int(board[x][y]) if board[x][y]!='E' else 0\n",
    "            s1,s2,s3,n1,n2,n3=-inf,-inf,-inf,0,0,0\n",
    "            temp=0\n",
    "            if x+1<n and self.dps[x+1][y]!='X':\n",
    "                dfs(x+1,y)\n",
    "                s1,n1 = self.dps[x+1][y],self.dpn[x+1][y]\n",
    "            if y+1<n and self.dps[x][y+1]!='X':\n",
    "                dfs(x,y+1)\n",
    "                s2,n2 = self.dps[x][y+1],self.dpn[x][y+1]\n",
    "            if x+1<n and y+1<n and self.dps[x+1][y+1]!='X':\n",
    "                dfs(x+1,y+1)\n",
    "                s3,n3 = self.dps[x+1][y+1],self.dpn[x+1][y+1]\n",
    "            if s1==max(s1,s2,s3):\n",
    "                temp += n1\n",
    "            if s2==max(s1,s2,s3):\n",
    "                temp += n2\n",
    "            if s3==max(s1,s2,s3):\n",
    "                temp += n3\n",
    "            self.dps[x][y] = max(s1,s2,s3)+s\n",
    "            self.dpn[x][y] = temp % MOD\n",
    "            self.visited[x][y]=True\n",
    "        dfs(0,0)\n",
    "        return [self.dps[0][0] if self.dps[0][0]!=-inf else 0, self.dpn[0][0]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def pathsWithMaxScore(self, board: List[str]) -> List[int]:\n",
    "#         n=len(board)\n",
    "#         MOD=10**9 + 7\n",
    "#         self.dps = [[-inf for _ in range(n)] for _ in range(n)]\n",
    "#         self.dpn = [[0 for _ in range(n)] for _ in range(n)]\n",
    "#         self.visited = [[False for _ in range(n)] for _ in range(n)]\n",
    "#         self.dps[n-1][n-1]=0\n",
    "#         self.dpn[n-1][n-1]=1\n",
    "#         def dfs(x, y):\n",
    "#             if self.visited[x][y]: return\n",
    "#             if board[x][y] in ['S','X']:\n",
    "#                 self.visited[x][y]=True\n",
    "#                 return\n",
    "#             s=int(board[x][y]) if board[x][y]!='E' else 0\n",
    "#             s1,s2,s3,n1,n2,n3=-inf,-inf,-inf,0,0,0\n",
    "#             temp=0\n",
    "#             if x+1<n and self.dps[x+1][y]!='X':\n",
    "#                 dfs(x+1,y)\n",
    "#                 s1,n1 = self.dps[x+1][y],self.dpn[x+1][y]\n",
    "#             if y+1<n and self.dps[x][y+1]!='X':\n",
    "#                 dfs(x,y+1)\n",
    "#                 s2,n2 = self.dps[x][y+1],self.dpn[x][y+1]\n",
    "#             if x+1<n and y+1<n and self.dps[x+1][y+1]!='X':\n",
    "#                 dfs(x+1,y+1)\n",
    "#                 s3,n3 = self.dps[x+1][y+1],self.dpn[x+1][y+1]\n",
    "#             if s1==max(s1,s2,s3):\n",
    "#                 temp += n1\n",
    "#             if s2==max(s1,s2,s3):\n",
    "#                 temp += n2\n",
    "#             if s3==max(s1,s2,s3):\n",
    "#                 temp += n3\n",
    "#             self.dps[x][y] = max(s1,s2,s3)+s\n",
    "#             self.dpn[x][y] = temp % MOD\n",
    "#             self.visited[x][y]=True\n",
    "#         # for i in range(n):\n",
    "#         #     for k in range(i): dfs(n-1-i,n-1-k)\n",
    "#         #     for k in range(i): dfs(n-1-k,n-1-i)\n",
    "#         #     dfs(n-1-i,n-1-i)\n",
    "#         dfs(0,0)\n",
    "#         # print(self.dps, self.dpn)\n",
    "#         return [self.dps[0][0] if self.dps[0][0]!=-inf else 0, self.dpn[0][0]]\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def pathsWithMaxScore(self, board: List[str]) -> List[int]:\n",
    "        n=len(board)\n",
    "        MOD=10**9 + 7\n",
    "        self.dps = [[-inf for _ in range(n)] for _ in range(n)]\n",
    "        self.dpn = [[0 for _ in range(n)] for _ in range(n)]\n",
    "        self.visited = [[False for _ in range(n)] for _ in range(n)]\n",
    "        self.dps[n-1][n-1]=0\n",
    "        self.dpn[n-1][n-1]=1\n",
    "        def dfs(x, y):\n",
    "            if self.visited[x][y]: return\n",
    "            if board[x][y] in ['S','X']:\n",
    "                self.visited[x][y]=True\n",
    "                return\n",
    "            s=int(board[x][y]) if board[x][y]!='E' else 0\n",
    "            s1,s2,s3,n1,n2,n3=-inf,-inf,-inf,0,0,0\n",
    "            temp=0\n",
    "            if x+1<n and self.dps[x+1][y]!='X':\n",
    "                dfs(x+1,y)\n",
    "                s1,n1 = self.dps[x+1][y],self.dpn[x+1][y]\n",
    "            if y+1<n and self.dps[x][y+1]!='X':\n",
    "                dfs(x,y+1)\n",
    "                s2,n2 = self.dps[x][y+1],self.dpn[x][y+1]\n",
    "            if x+1<n and y+1<n and self.dps[x+1][y+1]!='X':\n",
    "                dfs(x+1,y+1)\n",
    "                s3,n3 = self.dps[x+1][y+1],self.dpn[x+1][y+1]\n",
    "            if s1==max(s1,s2,s3):\n",
    "                temp += n1\n",
    "            if s2==max(s1,s2,s3):\n",
    "                temp += n2\n",
    "            if s3==max(s1,s2,s3):\n",
    "                temp += n3\n",
    "            self.dps[x][y] = max(s1,s2,s3)+s\n",
    "            self.dpn[x][y] = temp % MOD\n",
    "            self.visited[x][y]=True\n",
    "        dfs(0,0)\n",
    "        # print(self.dps, self.dpn)\n",
    "        return [self.dps[0][0] if self.dps[0][0]!=-inf else 0, self.dpn[0][0]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def pathsWithMaxScore(self, board: List[str]) -> List[int]:\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, j):\n",
    "            if i == j == m - 1:\n",
    "                return [0, 1]\n",
    "            res = [float(\"-inf\"), 0]\n",
    "            for x, y in [[i + 1, j + 1], [i + 1, j], [i, j + 1]]:\n",
    "                if 0 <= x < m and 0 <= y < m:\n",
    "                    nex = dfs(x, y)\n",
    "                    if res[0] < nex[0]:\n",
    "                        res = nex[:]\n",
    "                    elif res[0] == nex[0]:\n",
    "                        res[1] = (res[1] + nex[1]) % MOD\n",
    "            res[0] += dct[board[i][j]]\n",
    "            return res\n",
    "\n",
    "        dct = {str(i): i for i in range(10)}\n",
    "        dct[\"S\"] = 0\n",
    "        dct[\"E\"] = 0\n",
    "        dct[\"X\"] = float(\"-inf\")\n",
    "        m = len(board)\n",
    "        ans = dfs(0, 0)\n",
    "        return ans if ans[0] > float(\"-inf\") else [0, 0]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathsWithMaxScore(self, board: List[str]) -> List[int]:\n",
    "       n = len(board)\n",
    "       ways = [[0] * n for _ in range(n)]\n",
    "       ways[n - 1][n - 1] = 1\n",
    "       MOD = 10 ** 9 + 7\n",
    "\n",
    "       @cache\n",
    "       def dfs(i: int, j: int) -> int:\n",
    "          if i == n - 1 and j == n - 1:\n",
    "             return 0\n",
    "          if board[i][j] == 'X':\n",
    "             return -inf\n",
    "          res1 = -inf\n",
    "          res2 = -inf\n",
    "          res3 = -inf\n",
    "          if i + 1 < n:\n",
    "             res1 = dfs(i + 1, j)\n",
    "          if j + 1 < n:\n",
    "             res2 = dfs(i, j + 1)\n",
    "          if i + 1 < n and j + 1 < n:\n",
    "             res3 = dfs(i + 1, j + 1)\n",
    "          res = max(res1, res2, res3)\n",
    "          if res != -inf:\n",
    "             if res == res1:\n",
    "                ways[i][j] += ways[i + 1][j]\n",
    "                ways[i][j] %= MOD\n",
    "             if res == res2:\n",
    "                ways[i][j] += ways[i][j + 1]\n",
    "                ways[i][j] %= MOD\n",
    "             if res == res3:\n",
    "                ways[i][j] += ways[i + 1][j + 1]\n",
    "                ways[i][j] %= MOD\n",
    "          if not (i == 0 and j == 0):\n",
    "             res += ord(board[i][j]) - ord('0')\n",
    "          return res\n",
    "       res = dfs(0, 0)\n",
    "       if res < 0:\n",
    "          return [0, 0]\n",
    "       return [res, ways[0][0]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "DIRS = [[-1, 0], [0, -1], [-1, -1]]\n",
    "\n",
    "class Solution:\n",
    "    def pathsWithMaxScore(self, board: List[str]) -> List[int]:\n",
    "        m = len(board)\n",
    "        n = len(board[0])\n",
    "        @cache\n",
    "        def dfs(i: int, j: int) -> List[int]:\n",
    "            if i == 0 and j == 0: return [0, 1]\n",
    "            res = [0, 0]\n",
    "            for d in DIRS:\n",
    "                nx = i + d[0]\n",
    "                ny = j + d[1]\n",
    "                if nx >= 0 and ny >= 0 and board[nx][ny] != 'X':\n",
    "                    sub = dfs(nx, ny)\n",
    "                    if sub[0] > res[0]:\n",
    "                        res[0] = sub[0]\n",
    "                        res[1] = sub[1]\n",
    "                    elif sub[0] == res[0]:\n",
    "                        res[1] += sub[1]\n",
    "                        res[1] %= 1000000007\n",
    "            if res[1] != 0:\n",
    "                if board[i][j] != 'S':\n",
    "                    res[0] += int(board[i][j])\n",
    "            return res\n",
    "        return dfs(m - 1, n - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "mod= 10**9 + 7\n",
    "class Solution:\n",
    "    def pathsWithMaxScore(self, board: List[str]) -> List[int]:\n",
    "        board= [list(s) for s in board]\n",
    "        \n",
    "        m, n = len(board), len(board[0])\n",
    "        board[0][0] = board[-1][-1] = \"0\"\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dfs(i, j):\n",
    "            if i == m-1 and j == n-1:\n",
    "                return [0, 1]\n",
    "            res = [0, 0]\n",
    "            if i+1 < m and board[i+1][j] != \"X\":\n",
    "                s = int(board[i][j])\n",
    "                down = dfs(i+1, j)\n",
    "                if down[0]+s > res[0] and down[1]:\n",
    "                    res = [down[0]+s, down[1]]\n",
    "                elif down[0]+s == res[0]:\n",
    "                    res[1] += down[1]\n",
    "            if j+1<n and board[i][j+1] != \"X\":\n",
    "                s = int(board[i][j])\n",
    "                down = dfs(i, j+1)\n",
    "                if down[0]+s > res[0] and down[1]:\n",
    "                    res = [down[0]+s, down[1]]\n",
    "                elif down[0]+s == res[0]:\n",
    "                    res[1] += down[1]\n",
    "            if i+1<m and j+1<n and board[i+1][j+1] != \"X\":\n",
    "                s = int(board[i][j])\n",
    "                down = dfs(i+1, j+1)\n",
    "                if down[0]+s > res[0] and down[1]:\n",
    "                    res = [down[0]+s, down[1]]\n",
    "                elif down[0]+s == res[0]:\n",
    "                    res[1] += down[1]\n",
    "            res[1] %= mod\n",
    "            return res\n",
    "        \n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathsWithMaxScore(self, board: List[str]) -> List[int]:\n",
    "        n=len(board)\n",
    "        MAX=int(1e9+7)\n",
    "        def modify(lst):\n",
    "            if lst[1]==0:return [0,0]\n",
    "            return lst\n",
    "        @cache\n",
    "        def dfs(i,j):\n",
    "            if i==n-1 and j==n-1:return [0,1]\n",
    "            # 到头了只有三种情况\n",
    "            if i==0 and j==0:\n",
    "                lst=[dfs(i+1,j),dfs(i,j+1),dfs(i+1,j+1)]\n",
    "                key=max(lst[0][0],lst[1][0],lst[2][0])\n",
    "                value=0\n",
    "                for vector in lst:\n",
    "                    if vector[0]==key:value=(value+vector[1])%MAX\n",
    "                return [key,value]\n",
    "            if min(i,j)<0 or max(i,j)>=n or board[i][j]=='X':return [0,0]\n",
    "\n",
    "            lst=[dfs(i+1,j),dfs(i,j+1),dfs(i+1,j+1)]\n",
    "            key=max(lst[0][0], lst[1][0], lst[2][0])\n",
    "            value=0\n",
    "            for vector in lst:\n",
    "                if vector[0]==key:value=(value+vector[1])%MAX\n",
    "            return modify([key+int(board[i][j]),value])\n",
    "        return dfs(0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def pathsWithMaxScore(self, board: List[str]) -> List[int]:\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, j):\n",
    "            if i == j == m - 1:\n",
    "                return [0, 1]\n",
    "            res = [0, 0]\n",
    "            s = int(board[i][j])\n",
    "            for x, y in [[i + 1, j + 1], [i + 1, j], [i, j + 1]]:\n",
    "                if 0 <= x < m and 0 <= y < m and board[x][y] != \"X\":\n",
    "                    nex = dfs(x, y)[:]\n",
    "                    nex[0] += s\n",
    "                    if res[0] < nex[0] and nex[1]:\n",
    "                        res = nex[:]\n",
    "                    elif res[0] == nex[0] and nex[1]:\n",
    "                        res[1] += nex[1]\n",
    "            res[1] %= MOD\n",
    "            return res\n",
    "\n",
    "        m = len(board)\n",
    "        board = [list(s) for s in board]\n",
    "        board[0][0] = board[-1][-1] = \"0\"\n",
    "        ans = dfs(0, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathsWithMaxScore(self, board: List[str]) -> List[int]:\n",
    "        # 记忆化搜索\n",
    "        n = len(board)\n",
    "        mod = 10**9+7\n",
    "        @cache\n",
    "        def dfs(i,j):\n",
    "            # 表示从i,j出发到达E「得分」 的最大值，得到最大得分的方案数\n",
    "            if i == 0 and j == 0:\n",
    "                return [0,1]\n",
    "            cur = 0 if board[i][j] in 'SX' else int(board[i][j])\n",
    "            max_v = -inf\n",
    "            cnt = -inf\n",
    "            for x,y in (i,j-1),(i-1,j-1),(i-1,j):\n",
    "                if 0 <= x < n and  0 <= y < n and board[x][y] != 'X':\n",
    "                    a,b = dfs(x,y)\n",
    "                    if a > max_v:\n",
    "                        max_v,cnt= a,b\n",
    "                    elif a == max_v:\n",
    "                        cnt += b\n",
    "            if max_v == -inf:\n",
    "                return -inf,-inf\n",
    "            return [(max_v+cur),cnt%mod]\n",
    "\n",
    "        a,b = dfs(n-1,n-1)\n",
    "        return [0,0] if a == -inf else [a,b]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathsWithMaxScore(self, board: List[str]) -> List[int]:\n",
    "        mod = 10**9+7\n",
    "        n = len(board)\n",
    "        @ cache\n",
    "        def dfs(i,j):\n",
    "            # 表示从i,j出发到达左上角可以得到的分数最大值和最大得分的方案数\n",
    "            if i == 0 and j == 0:\n",
    "                return [0,1]\n",
    "            cur = 0 if board[i][j] in 'SX' else int(board[i][j])\n",
    "            max_v = -inf\n",
    "            cnt = -inf\n",
    "            for x,y in (i,j-1),(i-1,j-1),(i-1,j):\n",
    "                if 0 <= x < n and 0 <= y < n and board[x][y] != 'X':\n",
    "                    a,b = dfs(x,y)\n",
    "                    if a > max_v:\n",
    "                        max_v,cnt = a,b\n",
    "                    elif a == max_v:\n",
    "                        cnt += b\n",
    "            if max_v == -inf:\n",
    "                return -inf,-inf\n",
    "            return [(max_v+cur)%mod,cnt%mod]\n",
    "\n",
    "        a,b = dfs(n-1,n-1)\n",
    "        return [0,0] if a == -inf else [a,b]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
